From 55676a35757bcbf2fa40cc3fd144ba412c65b658 Mon Sep 17 00:00:00 2001 From: Runxi Yu Date: Tue, 9 Jun 2026 05:15:58 +0000 Subject: internal/cache: add (and move clock to internal/cache/clock) --- internal/cache/clock/bench_test.go | 109 +++++++++++++++++++++++ internal/cache/clock/cache.go | 86 ++++++++++++++++++ internal/cache/clock/cache_ops.go | 51 +++++++++++ internal/cache/clock/cache_test.go | 100 +++++++++++++++++++++ internal/cache/clock/concurrent_test.go | 103 ++++++++++++++++++++++ internal/cache/clock/doc.go | 9 ++ internal/cache/clock/fuzz_test.go | 53 ++++++++++++ internal/cache/clock/invariant_test.go | 88 +++++++++++++++++++ internal/cache/clock/shard.go | 67 ++++++++++++++ internal/cache/clock/shard_read.go | 33 +++++++ internal/cache/clock/shard_test.go | 149 ++++++++++++++++++++++++++++++++ internal/cache/clock/shard_write.go | 105 ++++++++++++++++++++++ internal/cache/doc.go | 2 + internal/clock/bench_test.go | 109 ----------------------- internal/clock/cache.go | 86 ------------------ internal/clock/cache_ops.go | 51 ----------- internal/clock/cache_test.go | 100 --------------------- internal/clock/concurrent_test.go | 103 ---------------------- internal/clock/doc.go | 9 -- internal/clock/fuzz_test.go | 53 ------------ internal/clock/invariant_test.go | 88 ------------------- internal/clock/shard.go | 67 -------------- internal/clock/shard_read.go | 33 ------- internal/clock/shard_test.go | 149 -------------------------------- internal/clock/shard_write.go | 105 ---------------------- 25 files changed, 955 insertions(+), 953 deletions(-) create mode 100644 internal/cache/clock/bench_test.go create mode 100644 internal/cache/clock/cache.go create mode 100644 internal/cache/clock/cache_ops.go create mode 100644 internal/cache/clock/cache_test.go create mode 100644 internal/cache/clock/concurrent_test.go create mode 100644 internal/cache/clock/doc.go create mode 100644 internal/cache/clock/fuzz_test.go create mode 100644 internal/cache/clock/invariant_test.go create mode 100644 internal/cache/clock/shard.go create mode 100644 internal/cache/clock/shard_read.go create mode 100644 internal/cache/clock/shard_test.go create mode 100644 internal/cache/clock/shard_write.go create mode 100644 internal/cache/doc.go delete mode 100644 internal/clock/bench_test.go delete mode 100644 internal/clock/cache.go delete mode 100644 internal/clock/cache_ops.go delete mode 100644 internal/clock/cache_test.go delete mode 100644 internal/clock/concurrent_test.go delete mode 100644 internal/clock/doc.go delete mode 100644 internal/clock/fuzz_test.go delete mode 100644 internal/clock/invariant_test.go delete mode 100644 internal/clock/shard.go delete mode 100644 internal/clock/shard_read.go delete mode 100644 internal/clock/shard_test.go delete mode 100644 internal/clock/shard_write.go (limited to 'internal') diff --git a/internal/cache/clock/bench_test.go b/internal/cache/clock/bench_test.go new file mode 100644 index 00000000..49d85cde --- /dev/null +++ b/internal/cache/clock/bench_test.go @@ -0,0 +1,109 @@ +package clock //nolint:testpackage + +import ( + "sync/atomic" + "testing" +) + +func benchWeight(_, _ int) uint64 { return 1 } + +// goroutineSeq hands each parallel worker a distinct starting offset +// so workers don't go in lockstep over identical keys. +var goroutineSeq atomic.Uint64 + +func workerOffset() int { + return int(goroutineSeq.Add(1) * 0x9E3779B1) +} + +func BenchmarkReadHeavy(b *testing.B) { + // ≈95% Get hits, ≈5% Add, and fits budget. + + const n = 100_000 + + cache := New(n, benchWeight) + for k := range n { + cache.Add(k, k) + } + + b.ResetTimer() + b.RunParallel(func(pb *testing.PB) { + i := workerOffset() + for pb.Next() { + i++ + key := i % n + if i%20 == 0 { + cache.Add(key, key) + } else { + _, _ = cache.Get(key) + } + } + }) +} + +func BenchmarkHotKey(b *testing.B) { + // Every worker does Get over a relatively small hot set. + + const ( + hot = 64 + maxWeight = 4096 + ) + + cache := New(maxWeight, benchWeight) + for k := range hot { + cache.Add(k, k) + } + + b.ResetTimer() + b.RunParallel(func(pb *testing.PB) { + i := workerOffset() + for pb.Next() { + i++ + _, _ = cache.Get(i % hot) + } + }) +} + +func BenchmarkMixed(b *testing.B) { + // Even split of Get and Add over a working set that fits. + + const n = 100_000 + + cache := New(n, benchWeight) + for k := range n { + cache.Add(k, k) + } + + b.ResetTimer() + b.RunParallel(func(pb *testing.PB) { + i := workerOffset() + for pb.Next() { + i++ + key := i % n + if i%2 == 0 { + cache.Add(key, key) + } else { + _, _ = cache.Get(key) + } + } + }) +} + +func BenchmarkChurn(b *testing.B) { + // Every op inserts a fresh key into a small budget. + // I don't think this is likely to happen for git delta caches, + // but this may matter if we use this for other workloads later. + + const maxWeight = 4096 + + cache := New(maxWeight, benchWeight) + + b.ResetTimer() + b.RunParallel(func(pb *testing.PB) { + base := workerOffset() + i := 0 + for pb.Next() { + i++ + cache.Add(base+i, i) + } + }) +} diff --git a/internal/cache/clock/cache.go b/internal/cache/clock/cache.go new file mode 100644 index 00000000..31d97082 --- /dev/null +++ b/internal/cache/clock/cache.go @@ -0,0 +1,86 @@ +package clock + +import ( + "hash/maphash" + "runtime" + + "lindenii.org/go/lgo/intconv" +) + +// maxShards bounds the shard count. +// +// Keep it relatively modest +// so the per-shard budget +// stays large enough to admit sizable values. +const maxShards = 16 + +// WeightFunc reports one entry's weight, used for eviction budgeting. +type WeightFunc[K comparable, V any] func(key K, value V) uint64 + +// Cache is a concurrent, weight-bounded cache +// with CLOCK eviction. +// +// Reads are lock-free; +// writes lock only the shard that owns the key. +// +// Labels: MT-Safe. +type Cache[K comparable, V any] struct { + shards []*shard[K, V] + seed maphash.Seed + mask uint64 + weightFn WeightFunc[K, V] +} + +// New returns a cache bounded to maxWeight total weight, +// weighing entries with weightFn. +// +// New panics if weightFn is nil. +func New[K comparable, V any](maxWeight uint64, weightFn WeightFunc[K, V]) *Cache[K, V] { + if weightFn == nil { + panic("internal/clock: nil weight function") + } + + count, mask := shardLayout(maxWeight) + perShard := maxWeight / (mask + 1) + + shards := make([]*shard[K, V], count) + for i := range shards { + shards[i] = newShard[K, V](perShard) + } + + return &Cache[K, V]{ + shards: shards, + seed: maphash.MakeSeed(), + mask: mask, + weightFn: weightFn, + } +} + +// shardLayout picks a power-of-two shard count and its address mask. +// +// Tracks GOMAXPROCS, capped at maxShards, +// and is shrunk so the per-shard budget +// stays at least one while maxWeight is nonzero. +func shardLayout(maxWeight uint64) (int, uint64) { + count := 1 + for count < runtime.GOMAXPROCS(0) && count < maxShards { + count *= 2 + } + + countU, err := intconv.IntToUint64(count) + if err != nil { + return 1, 0 + } + + for countU > maxWeight && countU > 1 { + count /= 2 + countU /= 2 + } + + return count, countU - 1 +} + +// shardFor returns the shard that owns key. +func (cache *Cache[K, V]) shardFor(key K) *shard[K, V] { + return cache.shards[maphash.Comparable(cache.seed, key)&cache.mask] +} diff --git a/internal/cache/clock/cache_ops.go b/internal/cache/clock/cache_ops.go new file mode 100644 index 00000000..18958202 --- /dev/null +++ b/internal/cache/clock/cache_ops.go @@ -0,0 +1,51 @@ +package clock + +// Add inserts or replaces key, marking it recently used. +// +// It reports whether the entry was admitted; +// an entry heavier than the per-shard budget is rejected +// and leaves the cache unchanged. +func (cache *Cache[K, V]) Add(key K, value V) bool { + return cache.shardFor(key).add(key, value, cache.weightFn(key, value)) +} + +// Get returns the value for key and marks it recently used. +// +//nolint:ireturn +func (cache *Cache[K, V]) Get(key K) (V, bool) { + return cache.shardFor(key).get(key) +} + +// Peek returns the value for key without changing its recency. +// +//nolint:ireturn +func (cache *Cache[K, V]) Peek(key K) (V, bool) { + return cache.shardFor(key).peek(key) +} + +// Len returns the number of cached entries. +func (cache *Cache[K, V]) Len() int { + total := 0 + for _, shard := range cache.shards { + total += shard.len() + } + + return total +} + +// Weight returns the current total weight across all shards. +func (cache *Cache[K, V]) Weight() uint64 { + var total uint64 + for _, shard := range cache.shards { + total += shard.loadWeight() + } + + return total +} + +// Clear removes all entries. +func (cache *Cache[K, V]) Clear() { + for _, shard := range cache.shards { + shard.clear() + } +} diff --git a/internal/cache/clock/cache_test.go b/internal/cache/clock/cache_test.go new file mode 100644 index 00000000..3d734b39 --- /dev/null +++ b/internal/cache/clock/cache_test.go @@ -0,0 +1,100 @@ +package clock_test + +import ( + "fmt" + "strings" + "testing" + + "lindenii.org/go/furgit/internal/cache/clock" + "lindenii.org/go/lgo/intconv" +) + +func byteWeight(_ string, value string) uint64 { + weight, err := intconv.IntToUint64(len(value)) + if err != nil { + return 0 + } + + return weight +} + +func TestCacheAddGetPeek(t *testing.T) { + t.Parallel() + + cache := clock.New(1<<20, byteWeight) + + if !cache.Add("a", "alpha") { + t.Fatalf("Add(a) should succeed") + } + + if got, ok := cache.Get("a"); !ok || got != "alpha" { + t.Fatalf("Get(a) = (%q, %v), want (alpha, true)", got, ok) + } + + if got, ok := cache.Peek("a"); !ok || got != "alpha" { + t.Fatalf("Peek(a) = (%q, %v), want (alpha, true)", got, ok) + } + + if _, ok := cache.Get("missing"); ok { + t.Fatalf("Get(missing) should miss") + } +} + +func TestCacheWeightStaysBounded(t *testing.T) { + t.Parallel() + + const maxWeight = 4096 + + cache := clock.New(maxWeight, byteWeight) + value := strings.Repeat("x", 64) + + for i := range 1000 { + cache.Add(fmt.Sprintf("key-%d", i), value) + } + + if got := cache.Weight(); got > maxWeight { + t.Fatalf("weight = %d, exceeds max %d", got, maxWeight) + } +} + +func TestCacheLenAndClear(t *testing.T) { + t.Parallel() + + cache := clock.New(1<<20, byteWeight) + + for i := range 10 { + cache.Add(fmt.Sprintf("key-%d", i), "v") + } + + if got := cache.Len(); got != 10 { + t.Fatalf("Len = %d, want 10", got) + } + + cache.Clear() + + if got := cache.Len(); got != 0 { + t.Fatalf("Len after Clear = %d, want 0", got) + } + + if got := cache.Weight(); got != 0 { + t.Fatalf("Weight after Clear = %d, want 0", got) + } +} + +func TestCacheRejectsOversized(t *testing.T) { + t.Parallel() + + cache := clock.New(4, byteWeight) + + if cache.Add("a", "xxxxx") { + t.Fatalf("oversized Add should report false") + } + + if _, ok := cache.Get("a"); ok { + t.Fatalf("oversized entry must not be cached") + } + + if got := cache.Weight(); got != 0 { + t.Fatalf("weight = %d, want 0", got) + } +} diff --git a/internal/cache/clock/concurrent_test.go b/internal/cache/clock/concurrent_test.go new file mode 100644 index 00000000..86283a9b --- /dev/null +++ b/internal/cache/clock/concurrent_test.go @@ -0,0 +1,103 @@ +package clock //nolint:testpackage + +import ( + "sync" + "testing" +) + +func keyValue(key int) int { + return key*1000003 + 7 +} + +func TestConcurrentStress(t *testing.T) { + t.Parallel() + + const ( + maxWeight = 512 + keys = 400 + workers = 8 + rounds = 5000 + ) + + cache := New(maxWeight, func(_ int, _ int) uint64 { return 1 }) + + var wg sync.WaitGroup + + for worker := range workers { + wg.Go(func() { + for i := range rounds { + key := (worker*7 + i) % keys + + switch i % 4 { + case 0, 1: + cache.Add(key, keyValue(key)) + case 2: + if got, ok := cache.Get(key); ok && got != keyValue(key) { + t.Errorf("Get(%d) = %d, want %d", key, got, keyValue(key)) + } + case 3: + if got, ok := cache.Peek(key); ok && got != keyValue(key) { + t.Errorf("Peek(%d) = %d, want %d", key, got, keyValue(key)) + } + } + } + }) + } + + wg.Wait() + + checkCache(t, cache) + + if got := cache.Weight(); got > maxWeight { + t.Fatalf("weight %d exceeds max %d", got, maxWeight) + } +} + +func TestReadDuringEviction(t *testing.T) { + t.Parallel() + + const ( + maxWeight = 8 + hot = 64 + writers = 2 + readers = 6 + rounds = 20000 + ) + + cache := New(maxWeight, func(_ int, _ int) uint64 { return 1 }) + + var wg sync.WaitGroup + + for range writers { + wg.Go(func() { + for i := range rounds { + key := i % hot + cache.Add(key, keyValue(key)) + } + }) + } + + for range readers { + wg.Go(func() { + for i := range rounds { + key := i % hot + + if got, ok := cache.Get(key); ok && got != keyValue(key) { + t.Errorf("Get(%d) = %d, want %d", key, got, keyValue(key)) + } + + if got, ok := cache.Peek(key); ok && got != keyValue(key) { + t.Errorf("Peek(%d) = %d, want %d", key, got, keyValue(key)) + } + } + }) + } + + wg.Wait() + + checkCache(t, cache) + + if got := cache.Weight(); got > maxWeight { + t.Fatalf("weight %d exceeds max %d", got, maxWeight) + } +} diff --git a/internal/cache/clock/doc.go b/internal/cache/clock/doc.go new file mode 100644 index 00000000..6f28805b --- /dev/null +++ b/internal/cache/clock/doc.go @@ -0,0 +1,9 @@ +// Package clock provides a concurrent, weight-bounded object cache. +// +// The cache is sharded by key, +// and each shard owns an independent fraction of the total budget. +// An entry heavier than that per-shard fraction is never admitted, +// so callers should keep the total budget well above the largest value. +// +// Labels: MT-Safe. +package clock diff --git a/internal/cache/clock/fuzz_test.go b/internal/cache/clock/fuzz_test.go new file mode 100644 index 00000000..af0d4024 --- /dev/null +++ b/internal/cache/clock/fuzz_test.go @@ -0,0 +1,53 @@ +package clock //nolint:testpackage + +import "testing" + +// FuzzShard replays a decoded op stream against one shard, +// checking the value oracle and invariants after every op. +func FuzzShard(f *testing.F) { + f.Add([]byte{}) + f.Add([]byte{0, 1, 10, 0, 2, 10, 0, 3, 10, 0, 4, 10, 1, 1, 0, 0, 5, 10}) + f.Add([]byte{0, 7, 200, 0, 7, 5, 2, 7, 0, 3, 0, 0, 0, 8, 8}) + + f.Fuzz(func(t *testing.T, program []byte) { + const maxWeight = 32 + + shard := newShard[uint8, uint64](maxWeight) + shadow := make(map[uint8]uint64) + + var nonce uint64 + + for i := 0; i+2 < len(program); i += 3 { + key := program[i+1] + weight := uint64(program[i+2]) + + switch program[i] % 4 { + case 0: // add + nonce++ + value := nonce + + admitted := shard.add(key, value, weight) + if admitted != (weight <= maxWeight) { + t.Fatalf("add(%d, w=%d) admitted=%v, want %v", key, weight, admitted, weight <= maxWeight) + } + + if admitted { + shadow[key] = value + } + case 1: // get + if got, ok := shard.get(key); ok && got != shadow[key] { + t.Fatalf("get(%d) = %d, want %d", key, got, shadow[key]) + } + case 2: // peek + if got, ok := shard.peek(key); ok && got != shadow[key] { + t.Fatalf("peek(%d) = %d, want %d", key, got, shadow[key]) + } + case 3: // clear + shard.clear() + clear(shadow) + } + + checkShard(t, shard) + } + }) +} diff --git a/internal/cache/clock/invariant_test.go b/internal/cache/clock/invariant_test.go new file mode 100644 index 00000000..2efd7ff9 --- /dev/null +++ b/internal/cache/clock/invariant_test.go @@ -0,0 +1,88 @@ +package clock //nolint:testpackage + +import "testing" + +// checkShard verifies a shard's structural invariants at a quiescent point. +// +// It must be called with no concurrent operations in flight. +func checkShard[K comparable, V any](t *testing.T, shard *shard[K, V]) { + t.Helper() + + shard.mu.Lock() + defer shard.mu.Unlock() + + ringLen := 0 + + var ringWeight uint64 + + seen := make(map[*entry[K, V]]struct{}) + + if shard.hand != nil { //nolint:nestif + for e := shard.hand; ; e = e.next { + if e.prev == nil || e.next == nil { + t.Fatalf("nil ring link at key %v", e.key) + } + + if e.next.prev != e || e.prev.next != e { + t.Fatalf("ring links not reciprocal at key %v", e.key) + } + + if _, dup := seen[e]; dup { + t.Fatalf("ring revisits a node before returning to the hand") + } + + seen[e] = struct{}{} + ringLen++ + ringWeight += e.weight + + if got, ok := shard.items.Load(e.key); !ok || got != e { + t.Fatalf("ring node %v is not mapped to itself", e.key) + } + + if e.next == shard.hand { + break + } + } + } + + if ringLen != shard.count { + t.Fatalf("ring length %d != count %d", ringLen, shard.count) + } + + if ringWeight != shard.weight { + t.Fatalf("ring weight %d != shard weight %d", ringWeight, shard.weight) + } + + if shard.weight > shard.maxWeight { + t.Fatalf("weight %d exceeds budget %d", shard.weight, shard.maxWeight) + } + + if (shard.hand == nil) != (shard.count == 0) { + t.Fatalf("hand/count disagree: hand=%v count=%d", shard.hand, shard.count) + } + + mapLen := 0 + + shard.items.Range(func(_ K, e *entry[K, V]) bool { + mapLen++ + + if _, ok := seen[e]; !ok { + t.Fatalf("mapped entry %v missing from ring", e.key) + } + + return true + }) + + if mapLen != shard.count { + t.Fatalf("map size %d != count %d", mapLen, shard.count) + } +} + +// checkCache verifies every shard's invariants. +func checkCache[K comparable, V any](t *testing.T, cache *Cache[K, V]) { + t.Helper() + + for _, shard := range cache.shards { + checkShard(t, shard) + } +} diff --git a/internal/cache/clock/shard.go b/internal/cache/clock/shard.go new file mode 100644 index 00000000..22e58b2f --- /dev/null +++ b/internal/cache/clock/shard.go @@ -0,0 +1,67 @@ +package clock + +import ( + "sync" + "sync/atomic" + + lsync "lindenii.org/go/lgo/sync" +) + +// entry is one cached key/value with CLOCK. +type entry[K comparable, V any] struct { + key K + value V + weight uint64 + prev, next *entry[K, V] + + // referenced is set on access and cleared by the eviction sweep; + // prev and next link the entry into its shard's ring. + referenced atomic.Bool +} + +// shard is an independently locked CLOCK cache. +type shard[K comparable, V any] struct { + items lsync.Map[K, *entry[K, V]] + + hand *entry[K, V] + weight uint64 + count int + maxWeight uint64 + + // mu protects the ring, hand, totals, and writes. + mu sync.Mutex +} + +// newShard returns an empty shard with the given weight budget. +func newShard[K comparable, V any](maxWeight uint64) *shard[K, V] { + return &shard[K, V]{ //nolint:exhaustruct + maxWeight: maxWeight, + } +} + +// len returns the shard's entry count. +func (shard *shard[K, V]) len() int { + shard.mu.Lock() + defer shard.mu.Unlock() + + return shard.count +} + +// loadWeight returns the shard's current total weight. +func (shard *shard[K, V]) loadWeight() uint64 { + shard.mu.Lock() + defer shard.mu.Unlock() + + return shard.weight +} + +// clear removes every entry. +func (shard *shard[K, V]) clear() { + shard.mu.Lock() + defer shard.mu.Unlock() + + shard.items.Clear() + shard.hand = nil + shard.weight = 0 + shard.count = 0 +} diff --git a/internal/cache/clock/shard_read.go b/internal/cache/clock/shard_read.go new file mode 100644 index 00000000..624e3409 --- /dev/null +++ b/internal/cache/clock/shard_read.go @@ -0,0 +1,33 @@ +package clock + +// get returns the value for key and marks it referenced. +// +//nolint:ireturn +func (shard *shard[K, V]) get(key K) (V, bool) { + e, ok := shard.items.Load(key) + if !ok { + var zero V + + return zero, false + } + + if !e.referenced.Load() { + e.referenced.Store(true) + } + + return e.value, true +} + +// peek returns the value for key without affecting eviction. +// +//nolint:ireturn +func (shard *shard[K, V]) peek(key K) (V, bool) { + e, ok := shard.items.Load(key) + if !ok { + var zero V + + return zero, false + } + + return e.value, true +} diff --git a/internal/cache/clock/shard_test.go b/internal/cache/clock/shard_test.go new file mode 100644 index 00000000..d974a30e --- /dev/null +++ b/internal/cache/clock/shard_test.go @@ -0,0 +1,149 @@ +package clock //nolint:testpackage + +import "testing" + +func TestShardEvictsOldest(t *testing.T) { + t.Parallel() + + shard := newShard[string, string](8) + shard.add("a", "a", 4) + shard.add("b", "b", 4) + shard.add("c", "c", 4) // overflows, evicts + + if _, ok := shard.peek("a"); ok { + t.Fatalf("a should have been evicted") + } + + for _, key := range []string{"b", "c"} { + if _, ok := shard.peek(key); !ok { + t.Fatalf("%s should remain present", key) + } + } + + if got := shard.loadWeight(); got != 8 { + t.Fatalf("weight = %d, want 8", got) + } + + if got := shard.len(); got != 2 { + t.Fatalf("len = %d, want 2", got) + } +} + +func TestShardGetGivesSecondChance(t *testing.T) { + t.Parallel() + + shard := newShard[string, string](8) + shard.add("a", "a", 4) + shard.add("b", "b", 4) + shard.add("c", "c", 4) // a evicted; b and c survive + + if _, ok := shard.get("b"); !ok { + t.Fatalf("get(b) should hit") + } + + shard.add("d", "d", 4) // b was just touched, so c is evicted instead + + if _, ok := shard.peek("c"); ok { + t.Fatalf("c should have been evicted after b was touched") + } + + for _, key := range []string{"b", "d"} { + if _, ok := shard.peek(key); !ok { + t.Fatalf("%s should remain present", key) + } + } +} + +func TestShardPeekGivesNoSecondChance(t *testing.T) { + t.Parallel() + + shard := newShard[string, string](8) + shard.add("a", "a", 4) + shard.add("b", "b", 4) + shard.add("c", "c", 4) // a is evicted; b and c survive with cleared bits + + if _, ok := shard.peek("b"); !ok { + t.Fatalf("peek(b) should hit") + } + + shard.add("d", "d", 4) // peek did not refresh b, so b is evicted + + if _, ok := shard.peek("b"); ok { + t.Fatalf("b should have been evicted; peek must not grant a second chance") + } + + for _, key := range []string{"c", "d"} { + if _, ok := shard.peek(key); !ok { + t.Fatalf("%s should remain present", key) + } + } +} + +func TestShardReplaceUpdatesWeight(t *testing.T) { + t.Parallel() + + shard := newShard[string, string](100) + shard.add("a", "old", 4) + shard.add("a", "new", 6) + + if got, ok := shard.peek("a"); !ok || got != "new" { + t.Fatalf("peek(a) = (%q, %v), want (new, true)", got, ok) + } + + if got := shard.loadWeight(); got != 6 { + t.Fatalf("weight = %d, want 6", got) + } + + if got := shard.len(); got != 1 { + t.Fatalf("len = %d, want 1", got) + } +} + +func TestShardRejectsOversized(t *testing.T) { + t.Parallel() + + shard := newShard[string, string](5) + shard.add("a", "x", 3) + + if shard.add("b", "big", 6) { + t.Fatalf("oversized add should report false") + } + + if shard.add("a", "huge", 6) { + t.Fatalf("oversized replace should report false") + } + + if got, ok := shard.peek("a"); !ok || got != "x" { + t.Fatalf("peek(a) = (%q, %v), want (x, true); cache must be unchanged", got, ok) + } + + if _, ok := shard.peek("b"); ok { + t.Fatalf("b must not have been admitted") + } + + if got := shard.loadWeight(); got != 3 { + t.Fatalf("weight = %d, want 3", got) + } +} + +func TestShardClear(t *testing.T) { + t.Parallel() + + shard := newShard[string, string](100) + shard.add("a", "a", 4) + shard.add("b", "b", 4) + + shard.clear() + + if got := shard.loadWeight(); got != 0 { + t.Fatalf("weight = %d, want 0", got) + } + + if got := shard.len(); got != 0 { + t.Fatalf("len = %d, want 0", got) + } + + if _, ok := shard.peek("a"); ok { + t.Fatalf("a should be gone after clear") + } +} diff --git a/internal/cache/clock/shard_write.go b/internal/cache/clock/shard_write.go new file mode 100644 index 00000000..40ddabd0 --- /dev/null +++ b/internal/cache/clock/shard_write.go @@ -0,0 +1,105 @@ +package clock + +// add inserts or replaces key, then evicts down to budget. +// +// It reports whether the entry was admitted; +// an entry heavier than the shard budget is rejected +// and leaves the shard unchanged. +func (shard *shard[K, V]) add(key K, value V, weight uint64) bool { + if weight > shard.maxWeight { + return false + } + + shard.mu.Lock() + defer shard.mu.Unlock() + + if old, ok := shard.items.Load(key); ok { + shard.unlink(old) + shard.items.Delete(key) + shard.weight -= old.weight + shard.count-- + } + + e := &entry[K, V]{ //nolint:exhaustruct + key: key, + value: value, + weight: weight, + } + e.referenced.Store(true) + + shard.linkBeforeHand(e) + shard.items.Store(key, e) + shard.weight += weight + shard.count++ + + shard.evict() + + return true +} + +// evict advances the clock hand until the shard is within budget. +// +// A referenced entry is spared once, its bit cleared; +// after a full rotation of spared entries the next is evicted regardless, +// so a flood of concurrent reads cannot stall progress. +func (shard *shard[K, V]) evict() { + skips := 0 + + for shard.weight > shard.maxWeight && shard.hand != nil { + victim := shard.hand + + if victim.referenced.Load() && skips < shard.count { + victim.referenced.Store(false) + shard.hand = victim.next + skips++ + + continue + } + + shard.unlink(victim) + shard.items.Delete(victim.key) + shard.weight -= victim.weight + shard.count-- + skips = 0 + } +} + +// linkBeforeHand inserts e just behind the hand, +// so a full rotation passes before the sweep examines it. +func (shard *shard[K, V]) linkBeforeHand(e *entry[K, V]) { + if shard.hand == nil { + e.prev = e + e.next = e + shard.hand = e + + return + } + + tail := shard.hand.prev + tail.next = e + e.prev = tail + e.next = shard.hand + shard.hand.prev = e +} + +// unlink removes e from the ring, +// moving the hand off e when it points at it. +func (shard *shard[K, V]) unlink(e *entry[K, V]) { + if e.next == e { + shard.hand = nil + e.prev = nil + e.next = nil + + return + } + + e.prev.next = e.next + e.next.prev = e.prev + + if shard.hand == e { + shard.hand = e.next + } + + e.prev = nil + e.next = nil +} diff --git a/internal/cache/doc.go b/internal/cache/doc.go new file mode 100644 index 00000000..2b4c454b --- /dev/null +++ b/internal/cache/doc.go @@ -0,0 +1,2 @@ +// Package cache provides caches for a few different access patterns. +package clock diff --git a/internal/clock/bench_test.go b/internal/clock/bench_test.go deleted file mode 100644 index 49d85cde..00000000 --- a/internal/clock/bench_test.go +++ /dev/null @@ -1,109 +0,0 @@ -package clock //nolint:testpackage - -import ( - "sync/atomic" - "testing" -) - -func benchWeight(_, _ int) uint64 { return 1 } - -// goroutineSeq hands each parallel worker a distinct starting offset -// so workers don't go in lockstep over identical keys. -var goroutineSeq atomic.Uint64 - -func workerOffset() int { - return int(goroutineSeq.Add(1) * 0x9E3779B1) -} - -func BenchmarkReadHeavy(b *testing.B) { - // ≈95% Get hits, ≈5% Add, and fits budget. - - const n = 100_000 - - cache := New(n, benchWeight) - for k := range n { - cache.Add(k, k) - } - - b.ResetTimer() - b.RunParallel(func(pb *testing.PB) { - i := workerOffset() - for pb.Next() { - i++ - key := i % n - if i%20 == 0 { - cache.Add(key, key) - } else { - _, _ = cache.Get(key) - } - } - }) -} - -func BenchmarkHotKey(b *testing.B) { - // Every worker does Get over a relatively small hot set. - - const ( - hot = 64 - maxWeight = 4096 - ) - - cache := New(maxWeight, benchWeight) - for k := range hot { - cache.Add(k, k) - } - - b.ResetTimer() - b.RunParallel(func(pb *testing.PB) { - i := workerOffset() - for pb.Next() { - i++ - _, _ = cache.Get(i % hot) - } - }) -} - -func BenchmarkMixed(b *testing.B) { - // Even split of Get and Add over a working set that fits. - - const n = 100_000 - - cache := New(n, benchWeight) - for k := range n { - cache.Add(k, k) - } - - b.ResetTimer() - b.RunParallel(func(pb *testing.PB) { - i := workerOffset() - for pb.Next() { - i++ - key := i % n - if i%2 == 0 { - cache.Add(key, key) - } else { - _, _ = cache.Get(key) - } - } - }) -} - -func BenchmarkChurn(b *testing.B) { - // Every op inserts a fresh key into a small budget. - // I don't think this is likely to happen for git delta caches, - // but this may matter if we use this for other workloads later. - - const maxWeight = 4096 - - cache := New(maxWeight, benchWeight) - - b.ResetTimer() - b.RunParallel(func(pb *testing.PB) { - base := workerOffset() - i := 0 - for pb.Next() { - i++ - cache.Add(base+i, i) - } - }) -} diff --git a/internal/clock/cache.go b/internal/clock/cache.go deleted file mode 100644 index 31d97082..00000000 --- a/internal/clock/cache.go +++ /dev/null @@ -1,86 +0,0 @@ -package clock - -import ( - "hash/maphash" - "runtime" - - "lindenii.org/go/lgo/intconv" -) - -// maxShards bounds the shard count. -// -// Keep it relatively modest -// so the per-shard budget -// stays large enough to admit sizable values. -const maxShards = 16 - -// WeightFunc reports one entry's weight, used for eviction budgeting. -type WeightFunc[K comparable, V any] func(key K, value V) uint64 - -// Cache is a concurrent, weight-bounded cache -// with CLOCK eviction. -// -// Reads are lock-free; -// writes lock only the shard that owns the key. -// -// Labels: MT-Safe. -type Cache[K comparable, V any] struct { - shards []*shard[K, V] - seed maphash.Seed - mask uint64 - weightFn WeightFunc[K, V] -} - -// New returns a cache bounded to maxWeight total weight, -// weighing entries with weightFn. -// -// New panics if weightFn is nil. -func New[K comparable, V any](maxWeight uint64, weightFn WeightFunc[K, V]) *Cache[K, V] { - if weightFn == nil { - panic("internal/clock: nil weight function") - } - - count, mask := shardLayout(maxWeight) - perShard := maxWeight / (mask + 1) - - shards := make([]*shard[K, V], count) - for i := range shards { - shards[i] = newShard[K, V](perShard) - } - - return &Cache[K, V]{ - shards: shards, - seed: maphash.MakeSeed(), - mask: mask, - weightFn: weightFn, - } -} - -// shardLayout picks a power-of-two shard count and its address mask. -// -// Tracks GOMAXPROCS, capped at maxShards, -// and is shrunk so the per-shard budget -// stays at least one while maxWeight is nonzero. -func shardLayout(maxWeight uint64) (int, uint64) { - count := 1 - for count < runtime.GOMAXPROCS(0) && count < maxShards { - count *= 2 - } - - countU, err := intconv.IntToUint64(count) - if err != nil { - return 1, 0 - } - - for countU > maxWeight && countU > 1 { - count /= 2 - countU /= 2 - } - - return count, countU - 1 -} - -// shardFor returns the shard that owns key. -func (cache *Cache[K, V]) shardFor(key K) *shard[K, V] { - return cache.shards[maphash.Comparable(cache.seed, key)&cache.mask] -} diff --git a/internal/clock/cache_ops.go b/internal/clock/cache_ops.go deleted file mode 100644 index 18958202..00000000 --- a/internal/clock/cache_ops.go +++ /dev/null @@ -1,51 +0,0 @@ -package clock - -// Add inserts or replaces key, marking it recently used. -// -// It reports whether the entry was admitted; -// an entry heavier than the per-shard budget is rejected -// and leaves the cache unchanged. -func (cache *Cache[K, V]) Add(key K, value V) bool { - return cache.shardFor(key).add(key, value, cache.weightFn(key, value)) -} - -// Get returns the value for key and marks it recently used. -// -//nolint:ireturn -func (cache *Cache[K, V]) Get(key K) (V, bool) { - return cache.shardFor(key).get(key) -} - -// Peek returns the value for key without changing its recency. -// -//nolint:ireturn -func (cache *Cache[K, V]) Peek(key K) (V, bool) { - return cache.shardFor(key).peek(key) -} - -// Len returns the number of cached entries. -func (cache *Cache[K, V]) Len() int { - total := 0 - for _, shard := range cache.shards { - total += shard.len() - } - - return total -} - -// Weight returns the current total weight across all shards. -func (cache *Cache[K, V]) Weight() uint64 { - var total uint64 - for _, shard := range cache.shards { - total += shard.loadWeight() - } - - return total -} - -// Clear removes all entries. -func (cache *Cache[K, V]) Clear() { - for _, shard := range cache.shards { - shard.clear() - } -} diff --git a/internal/clock/cache_test.go b/internal/clock/cache_test.go deleted file mode 100644 index 116efdd3..00000000 --- a/internal/clock/cache_test.go +++ /dev/null @@ -1,100 +0,0 @@ -package clock_test - -import ( - "fmt" - "strings" - "testing" - - "lindenii.org/go/furgit/internal/clock" - "lindenii.org/go/lgo/intconv" -) - -func byteWeight(_ string, value string) uint64 { - weight, err := intconv.IntToUint64(len(value)) - if err != nil { - return 0 - } - - return weight -} - -func TestCacheAddGetPeek(t *testing.T) { - t.Parallel() - - cache := clock.New(1<<20, byteWeight) - - if !cache.Add("a", "alpha") { - t.Fatalf("Add(a) should succeed") - } - - if got, ok := cache.Get("a"); !ok || got != "alpha" { - t.Fatalf("Get(a) = (%q, %v), want (alpha, true)", got, ok) - } - - if got, ok := cache.Peek("a"); !ok || got != "alpha" { - t.Fatalf("Peek(a) = (%q, %v), want (alpha, true)", got, ok) - } - - if _, ok := cache.Get("missing"); ok { - t.Fatalf("Get(missing) should miss") - } -} - -func TestCacheWeightStaysBounded(t *testing.T) { - t.Parallel() - - const maxWeight = 4096 - - cache := clock.New(maxWeight, byteWeight) - value := strings.Repeat("x", 64) - - for i := range 1000 { - cache.Add(fmt.Sprintf("key-%d", i), value) - } - - if got := cache.Weight(); got > maxWeight { - t.Fatalf("weight = %d, exceeds max %d", got, maxWeight) - } -} - -func TestCacheLenAndClear(t *testing.T) { - t.Parallel() - - cache := clock.New(1<<20, byteWeight) - - for i := range 10 { - cache.Add(fmt.Sprintf("key-%d", i), "v") - } - - if got := cache.Len(); got != 10 { - t.Fatalf("Len = %d, want 10", got) - } - - cache.Clear() - - if got := cache.Len(); got != 0 { - t.Fatalf("Len after Clear = %d, want 0", got) - } - - if got := cache.Weight(); got != 0 { - t.Fatalf("Weight after Clear = %d, want 0", got) - } -} - -func TestCacheRejectsOversized(t *testing.T) { - t.Parallel() - - cache := clock.New(4, byteWeight) - - if cache.Add("a", "xxxxx") { - t.Fatalf("oversized Add should report false") - } - - if _, ok := cache.Get("a"); ok { - t.Fatalf("oversized entry must not be cached") - } - - if got := cache.Weight(); got != 0 { - t.Fatalf("weight = %d, want 0", got) - } -} diff --git a/internal/clock/concurrent_test.go b/internal/clock/concurrent_test.go deleted file mode 100644 index 86283a9b..00000000 --- a/internal/clock/concurrent_test.go +++ /dev/null @@ -1,103 +0,0 @@ -package clock //nolint:testpackage - -import ( - "sync" - "testing" -) - -func keyValue(key int) int { - return key*1000003 + 7 -} - -func TestConcurrentStress(t *testing.T) { - t.Parallel() - - const ( - maxWeight = 512 - keys = 400 - workers = 8 - rounds = 5000 - ) - - cache := New(maxWeight, func(_ int, _ int) uint64 { return 1 }) - - var wg sync.WaitGroup - - for worker := range workers { - wg.Go(func() { - for i := range rounds { - key := (worker*7 + i) % keys - - switch i % 4 { - case 0, 1: - cache.Add(key, keyValue(key)) - case 2: - if got, ok := cache.Get(key); ok && got != keyValue(key) { - t.Errorf("Get(%d) = %d, want %d", key, got, keyValue(key)) - } - case 3: - if got, ok := cache.Peek(key); ok && got != keyValue(key) { - t.Errorf("Peek(%d) = %d, want %d", key, got, keyValue(key)) - } - } - } - }) - } - - wg.Wait() - - checkCache(t, cache) - - if got := cache.Weight(); got > maxWeight { - t.Fatalf("weight %d exceeds max %d", got, maxWeight) - } -} - -func TestReadDuringEviction(t *testing.T) { - t.Parallel() - - const ( - maxWeight = 8 - hot = 64 - writers = 2 - readers = 6 - rounds = 20000 - ) - - cache := New(maxWeight, func(_ int, _ int) uint64 { return 1 }) - - var wg sync.WaitGroup - - for range writers { - wg.Go(func() { - for i := range rounds { - key := i % hot - cache.Add(key, keyValue(key)) - } - }) - } - - for range readers { - wg.Go(func() { - for i := range rounds { - key := i % hot - - if got, ok := cache.Get(key); ok && got != keyValue(key) { - t.Errorf("Get(%d) = %d, want %d", key, got, keyValue(key)) - } - - if got, ok := cache.Peek(key); ok && got != keyValue(key) { - t.Errorf("Peek(%d) = %d, want %d", key, got, keyValue(key)) - } - } - }) - } - - wg.Wait() - - checkCache(t, cache) - - if got := cache.Weight(); got > maxWeight { - t.Fatalf("weight %d exceeds max %d", got, maxWeight) - } -} diff --git a/internal/clock/doc.go b/internal/clock/doc.go deleted file mode 100644 index 6f28805b..00000000 --- a/internal/clock/doc.go +++ /dev/null @@ -1,9 +0,0 @@ -// Package clock provides a concurrent, weight-bounded object cache. -// -// The cache is sharded by key, -// and each shard owns an independent fraction of the total budget. -// An entry heavier than that per-shard fraction is never admitted, -// so callers should keep the total budget well above the largest value. -// -// Labels: MT-Safe. -package clock diff --git a/internal/clock/fuzz_test.go b/internal/clock/fuzz_test.go deleted file mode 100644 index af0d4024..00000000 --- a/internal/clock/fuzz_test.go +++ /dev/null @@ -1,53 +0,0 @@ -package clock //nolint:testpackage - -import "testing" - -// FuzzShard replays a decoded op stream against one shard, -// checking the value oracle and invariants after every op. -func FuzzShard(f *testing.F) { - f.Add([]byte{}) - f.Add([]byte{0, 1, 10, 0, 2, 10, 0, 3, 10, 0, 4, 10, 1, 1, 0, 0, 5, 10}) - f.Add([]byte{0, 7, 200, 0, 7, 5, 2, 7, 0, 3, 0, 0, 0, 8, 8}) - - f.Fuzz(func(t *testing.T, program []byte) { - const maxWeight = 32 - - shard := newShard[uint8, uint64](maxWeight) - shadow := make(map[uint8]uint64) - - var nonce uint64 - - for i := 0; i+2 < len(program); i += 3 { - key := program[i+1] - weight := uint64(program[i+2]) - - switch program[i] % 4 { - case 0: // add - nonce++ - value := nonce - - admitted := shard.add(key, value, weight) - if admitted != (weight <= maxWeight) { - t.Fatalf("add(%d, w=%d) admitted=%v, want %v", key, weight, admitted, weight <= maxWeight) - } - - if admitted { - shadow[key] = value - } - case 1: // get - if got, ok := shard.get(key); ok && got != shadow[key] { - t.Fatalf("get(%d) = %d, want %d", key, got, shadow[key]) - } - case 2: // peek - if got, ok := shard.peek(key); ok && got != shadow[key] { - t.Fatalf("peek(%d) = %d, want %d", key, got, shadow[key]) - } - case 3: // clear - shard.clear() - clear(shadow) - } - - checkShard(t, shard) - } - }) -} diff --git a/internal/clock/invariant_test.go b/internal/clock/invariant_test.go deleted file mode 100644 index 2efd7ff9..00000000 --- a/internal/clock/invariant_test.go +++ /dev/null @@ -1,88 +0,0 @@ -package clock //nolint:testpackage - -import "testing" - -// checkShard verifies a shard's structural invariants at a quiescent point. -// -// It must be called with no concurrent operations in flight. -func checkShard[K comparable, V any](t *testing.T, shard *shard[K, V]) { - t.Helper() - - shard.mu.Lock() - defer shard.mu.Unlock() - - ringLen := 0 - - var ringWeight uint64 - - seen := make(map[*entry[K, V]]struct{}) - - if shard.hand != nil { //nolint:nestif - for e := shard.hand; ; e = e.next { - if e.prev == nil || e.next == nil { - t.Fatalf("nil ring link at key %v", e.key) - } - - if e.next.prev != e || e.prev.next != e { - t.Fatalf("ring links not reciprocal at key %v", e.key) - } - - if _, dup := seen[e]; dup { - t.Fatalf("ring revisits a node before returning to the hand") - } - - seen[e] = struct{}{} - ringLen++ - ringWeight += e.weight - - if got, ok := shard.items.Load(e.key); !ok || got != e { - t.Fatalf("ring node %v is not mapped to itself", e.key) - } - - if e.next == shard.hand { - break - } - } - } - - if ringLen != shard.count { - t.Fatalf("ring length %d != count %d", ringLen, shard.count) - } - - if ringWeight != shard.weight { - t.Fatalf("ring weight %d != shard weight %d", ringWeight, shard.weight) - } - - if shard.weight > shard.maxWeight { - t.Fatalf("weight %d exceeds budget %d", shard.weight, shard.maxWeight) - } - - if (shard.hand == nil) != (shard.count == 0) { - t.Fatalf("hand/count disagree: hand=%v count=%d", shard.hand, shard.count) - } - - mapLen := 0 - - shard.items.Range(func(_ K, e *entry[K, V]) bool { - mapLen++ - - if _, ok := seen[e]; !ok { - t.Fatalf("mapped entry %v missing from ring", e.key) - } - - return true - }) - - if mapLen != shard.count { - t.Fatalf("map size %d != count %d", mapLen, shard.count) - } -} - -// checkCache verifies every shard's invariants. -func checkCache[K comparable, V any](t *testing.T, cache *Cache[K, V]) { - t.Helper() - - for _, shard := range cache.shards { - checkShard(t, shard) - } -} diff --git a/internal/clock/shard.go b/internal/clock/shard.go deleted file mode 100644 index 22e58b2f..00000000 --- a/internal/clock/shard.go +++ /dev/null @@ -1,67 +0,0 @@ -package clock - -import ( - "sync" - "sync/atomic" - - lsync "lindenii.org/go/lgo/sync" -) - -// entry is one cached key/value with CLOCK. -type entry[K comparable, V any] struct { - key K - value V - weight uint64 - prev, next *entry[K, V] - - // referenced is set on access and cleared by the eviction sweep; - // prev and next link the entry into its shard's ring. - referenced atomic.Bool -} - -// shard is an independently locked CLOCK cache. -type shard[K comparable, V any] struct { - items lsync.Map[K, *entry[K, V]] - - hand *entry[K, V] - weight uint64 - count int - maxWeight uint64 - - // mu protects the ring, hand, totals, and writes. - mu sync.Mutex -} - -// newShard returns an empty shard with the given weight budget. -func newShard[K comparable, V any](maxWeight uint64) *shard[K, V] { - return &shard[K, V]{ //nolint:exhaustruct - maxWeight: maxWeight, - } -} - -// len returns the shard's entry count. -func (shard *shard[K, V]) len() int { - shard.mu.Lock() - defer shard.mu.Unlock() - - return shard.count -} - -// loadWeight returns the shard's current total weight. -func (shard *shard[K, V]) loadWeight() uint64 { - shard.mu.Lock() - defer shard.mu.Unlock() - - return shard.weight -} - -// clear removes every entry. -func (shard *shard[K, V]) clear() { - shard.mu.Lock() - defer shard.mu.Unlock() - - shard.items.Clear() - shard.hand = nil - shard.weight = 0 - shard.count = 0 -} diff --git a/internal/clock/shard_read.go b/internal/clock/shard_read.go deleted file mode 100644 index 624e3409..00000000 --- a/internal/clock/shard_read.go +++ /dev/null @@ -1,33 +0,0 @@ -package clock - -// get returns the value for key and marks it referenced. -// -//nolint:ireturn -func (shard *shard[K, V]) get(key K) (V, bool) { - e, ok := shard.items.Load(key) - if !ok { - var zero V - - return zero, false - } - - if !e.referenced.Load() { - e.referenced.Store(true) - } - - return e.value, true -} - -// peek returns the value for key without affecting eviction. -// -//nolint:ireturn -func (shard *shard[K, V]) peek(key K) (V, bool) { - e, ok := shard.items.Load(key) - if !ok { - var zero V - - return zero, false - } - - return e.value, true -} diff --git a/internal/clock/shard_test.go b/internal/clock/shard_test.go deleted file mode 100644 index d974a30e..00000000 --- a/internal/clock/shard_test.go +++ /dev/null @@ -1,149 +0,0 @@ -package clock //nolint:testpackage - -import "testing" - -func TestShardEvictsOldest(t *testing.T) { - t.Parallel() - - shard := newShard[string, string](8) - shard.add("a", "a", 4) - shard.add("b", "b", 4) - shard.add("c", "c", 4) // overflows, evicts - - if _, ok := shard.peek("a"); ok { - t.Fatalf("a should have been evicted") - } - - for _, key := range []string{"b", "c"} { - if _, ok := shard.peek(key); !ok { - t.Fatalf("%s should remain present", key) - } - } - - if got := shard.loadWeight(); got != 8 { - t.Fatalf("weight = %d, want 8", got) - } - - if got := shard.len(); got != 2 { - t.Fatalf("len = %d, want 2", got) - } -} - -func TestShardGetGivesSecondChance(t *testing.T) { - t.Parallel() - - shard := newShard[string, string](8) - shard.add("a", "a", 4) - shard.add("b", "b", 4) - shard.add("c", "c", 4) // a evicted; b and c survive - - if _, ok := shard.get("b"); !ok { - t.Fatalf("get(b) should hit") - } - - shard.add("d", "d", 4) // b was just touched, so c is evicted instead - - if _, ok := shard.peek("c"); ok { - t.Fatalf("c should have been evicted after b was touched") - } - - for _, key := range []string{"b", "d"} { - if _, ok := shard.peek(key); !ok { - t.Fatalf("%s should remain present", key) - } - } -} - -func TestShardPeekGivesNoSecondChance(t *testing.T) { - t.Parallel() - - shard := newShard[string, string](8) - shard.add("a", "a", 4) - shard.add("b", "b", 4) - shard.add("c", "c", 4) // a is evicted; b and c survive with cleared bits - - if _, ok := shard.peek("b"); !ok { - t.Fatalf("peek(b) should hit") - } - - shard.add("d", "d", 4) // peek did not refresh b, so b is evicted - - if _, ok := shard.peek("b"); ok { - t.Fatalf("b should have been evicted; peek must not grant a second chance") - } - - for _, key := range []string{"c", "d"} { - if _, ok := shard.peek(key); !ok { - t.Fatalf("%s should remain present", key) - } - } -} - -func TestShardReplaceUpdatesWeight(t *testing.T) { - t.Parallel() - - shard := newShard[string, string](100) - shard.add("a", "old", 4) - shard.add("a", "new", 6) - - if got, ok := shard.peek("a"); !ok || got != "new" { - t.Fatalf("peek(a) = (%q, %v), want (new, true)", got, ok) - } - - if got := shard.loadWeight(); got != 6 { - t.Fatalf("weight = %d, want 6", got) - } - - if got := shard.len(); got != 1 { - t.Fatalf("len = %d, want 1", got) - } -} - -func TestShardRejectsOversized(t *testing.T) { - t.Parallel() - - shard := newShard[string, string](5) - shard.add("a", "x", 3) - - if shard.add("b", "big", 6) { - t.Fatalf("oversized add should report false") - } - - if shard.add("a", "huge", 6) { - t.Fatalf("oversized replace should report false") - } - - if got, ok := shard.peek("a"); !ok || got != "x" { - t.Fatalf("peek(a) = (%q, %v), want (x, true); cache must be unchanged", got, ok) - } - - if _, ok := shard.peek("b"); ok { - t.Fatalf("b must not have been admitted") - } - - if got := shard.loadWeight(); got != 3 { - t.Fatalf("weight = %d, want 3", got) - } -} - -func TestShardClear(t *testing.T) { - t.Parallel() - - shard := newShard[string, string](100) - shard.add("a", "a", 4) - shard.add("b", "b", 4) - - shard.clear() - - if got := shard.loadWeight(); got != 0 { - t.Fatalf("weight = %d, want 0", got) - } - - if got := shard.len(); got != 0 { - t.Fatalf("len = %d, want 0", got) - } - - if _, ok := shard.peek("a"); ok { - t.Fatalf("a should be gone after clear") - } -} diff --git a/internal/clock/shard_write.go b/internal/clock/shard_write.go deleted file mode 100644 index 40ddabd0..00000000 --- a/internal/clock/shard_write.go +++ /dev/null @@ -1,105 +0,0 @@ -package clock - -// add inserts or replaces key, then evicts down to budget. -// -// It reports whether the entry was admitted; -// an entry heavier than the shard budget is rejected -// and leaves the shard unchanged. -func (shard *shard[K, V]) add(key K, value V, weight uint64) bool { - if weight > shard.maxWeight { - return false - } - - shard.mu.Lock() - defer shard.mu.Unlock() - - if old, ok := shard.items.Load(key); ok { - shard.unlink(old) - shard.items.Delete(key) - shard.weight -= old.weight - shard.count-- - } - - e := &entry[K, V]{ //nolint:exhaustruct - key: key, - value: value, - weight: weight, - } - e.referenced.Store(true) - - shard.linkBeforeHand(e) - shard.items.Store(key, e) - shard.weight += weight - shard.count++ - - shard.evict() - - return true -} - -// evict advances the clock hand until the shard is within budget. -// -// A referenced entry is spared once, its bit cleared; -// after a full rotation of spared entries the next is evicted regardless, -// so a flood of concurrent reads cannot stall progress. -func (shard *shard[K, V]) evict() { - skips := 0 - - for shard.weight > shard.maxWeight && shard.hand != nil { - victim := shard.hand - - if victim.referenced.Load() && skips < shard.count { - victim.referenced.Store(false) - shard.hand = victim.next - skips++ - - continue - } - - shard.unlink(victim) - shard.items.Delete(victim.key) - shard.weight -= victim.weight - shard.count-- - skips = 0 - } -} - -// linkBeforeHand inserts e just behind the hand, -// so a full rotation passes before the sweep examines it. -func (shard *shard[K, V]) linkBeforeHand(e *entry[K, V]) { - if shard.hand == nil { - e.prev = e - e.next = e - shard.hand = e - - return - } - - tail := shard.hand.prev - tail.next = e - e.prev = tail - e.next = shard.hand - shard.hand.prev = e -} - -// unlink removes e from the ring, -// moving the hand off e when it points at it. -func (shard *shard[K, V]) unlink(e *entry[K, V]) { - if e.next == e { - shard.hand = nil - e.prev = nil - e.next = nil - - return - } - - e.prev.next = e.next - e.next.prev = e.prev - - if shard.hand == e { - shard.hand = e.next - } - - e.prev = nil - e.next = nil -} -- cgit v1.3.1-10-gc9f91