buffer.go

// Locking invariants for *scopeBuffer
// -----------------------------------
//
//  1. Lock-acquisition order is strictly TOP-DOWN:
//     Store-level code may acquire scopeShard.mu BEFORE buf.mu.
//     Multi-shard ops additionally acquire shard.mu in ascending
//     shard-index order (see numShards comment in store.go).
//
//  2. scopeBuffer methods MUST NOT reach back up to acquire any
//     Store-level lock — neither scopeShard.mu nor any future
//     Store-side mutex — while holding b.mu. The only Store-state a
//     scopeBuffer method may touch with b.mu held is the atomic
//     counter (b.store.totalBytes.Add / b.store.reserveBytes); those
//     take no locks. Reverse-direction locking (buf → shard) would
//     deadlock against dropScope, replaceScopes, flush and
//     rebuildAll, all of which take shard.mu first and then
//     individual buf.mu's.
//
//  3. Read-path bookkeeping (recordRead) runs without taking b.mu —
//     it bumps the readCountTotal and lastAccessTS atomics directly.
//     This is what lets concurrent readers hold b.mu.RLock simultaneously
//     without serialising on the read counters. See recordRead in
//     buffer_heat.go.
//
//  4. items and byID hold *Item, and both indexes alias the SAME
//     *Item per entry. Seq-keyed access goes through indexBySeqLocked
//     (binary search on b.items, which is monotonic by seq). A method
//     may mutate an item's fields in place through either index under
//     b.mu.Lock — the other observes it with no re-sync. But a method
//     MUST NOT hand a raw *Item to a caller or retain one past the
//     unlock: read paths deref-copy into a value Item before returning.
//     A leaked *Item would let a caller mutate cache state outside b.mu.
//
// Adding a new scopeBuffer method that violates rule 2 is the most
// likely future deadlock — flag it in code review.
//
// File layout for scopeBuffer methods:
//
//	buffer.go          — struct + ctor + this invariant header
//	buffer_locked.go   — cross-cutting helpers (precomputeRawBytes,
//	                     indexBySeqLocked, replaceItemFieldsLocked,
//	                     reservePayloadDeltaLocked)
//	buffer_heat.go     — lock-free recordRead bookkeeping
//	buffer_write.go    — appendItem, upsertByID, updateByID, updateBySeq
//	buffer_delete.go   — deleteByID, deleteBySeq, trimSeq, deleteIndexLocked
//	buffer_replace.go  — scopeReplacement type, build / commit pipeline, replaceAll
//	buffer_read.go     — tailOffset, sinceSeq, getByID, getBySeq
//	buffer_stats.go    — approxSizeBytes, scopeStats type, stats()

package scopecache

import (
	"sync"
	"sync/atomic"
)

// Per-scope Item storage uses a chunk allocator: Items live in fixed,
// never-moved blocks, and the *Item stored in items/byID is &block[i],
// stable for the item's lifetime so the index aliasing holds.
//
// Block sizes grow geometrically (1, 4, 16, … capped at 1024), so a
// one-item scope costs exactly one Item while a large scope amortises
// to ~one alloc per 1024 items. Deleted slots recycle within the scope
// via the freeList, so append-delete-append churn settles at zero block
// allocs. A scope drained to empty drops its blocks (resetIfEmptyLocked)
// to reclaim the memory.
var itemChunkSizes = [...]int{1, 4, 16, 64, 256, 1024}

func nextItemChunkSize(existingChunks int) int {
	if existingChunks < len(itemChunkSizes) {
		return itemChunkSizes[existingChunks]
	}
	return itemChunkSizes[len(itemChunkSizes)-1]
}

// itemChunkReclaimThreshold is the per-scope Item-chunk capacity below
// which a drained-to-empty scope KEEPS its blocks + freeList (+ maps,
// items slice) instead of dropping them. A scope oscillating around
// empty — churn, or a drain-stream refilling after trim —
// reuses that storage at zero allocations (the old slab-pool's job).
// A scope that grew past it returns the memory on full drain.
const itemChunkReclaimThreshold = 256

type scopeBuffer struct {
	mu sync.RWMutex
	// store is always non-nil: production buffers are built by
	// s.newscopeBuffer() and bind to their owning store, test buffers
	// go through newTestBuffer which wires a permissive private store
	// internally. The per-scope item-count cap and per-item byte cap
	// both read from b.store directly so admission rules cannot drift
	// between a per-scope cache and the store-level source of truth.
	store *store
	// scope is the canonical scope-name string for this buffer — the
	// SAME Go string the shard map uses as its key. Every insert path
	// stamps item.Scope = b.scope, so all N items in a scope share one
	// underlying byte allocation instead of carrying N independent
	// copies of the fresh JSON-decoded scope string. ~20-35% live-heap
	// shave on long-scope-name workloads (multi-tenant `<token>:<scope>`).
	scope string
	// detached is set true when the buffer has been unlinked from its Store
	// by /drop_scope, /flush or /rebuild. Writes that reach a detached
	// buffer via a stale pointer return *ScopeDetachedError so the caller
	// learns the write did not take effect, rather than silently writing
	// into an orphan buffer that is unreachable and about to be GC'd.
	detached bool
	// items and byID are pointer collections: every entry for a given
	// item is the SAME *Item. An in-place field write through either
	// index is visible through the other — no re-sync needed. The
	// insert paths (insertNewItemLocked, buildReplacementState) must
	// therefore store one shared pointer into both; read paths must
	// deref-copy before handing an item out so a caller never holds
	// the live *Item.
	//
	// Seq-keyed access (getBySeq, deleteBySeq, updateBySeq) uses
	// indexBySeqLocked: O(log N) binary search on b.items, which is
	// always monotonic ascending by Seq. A previous map[uint64]*Item
	// secondary index was removed — its mapassign cost dominated the
	// append hot path while its O(1) lookup advantage was invisible
	// against the binary-search alternative for any realistic scope
	// size (≤ 14 comparisons for 10k items).
	items   []*Item
	byID    map[string]*Item
	lastSeq uint64
	// itemChunks is the per-scope Item storage: fixed, never-moved
	// blocks. Every *Item in items/byID points into one of them
	// (&block[i]); blocks never realloc, so those pointers stay valid
	// for the item's lifetime. chunkUsed is the fill level of the last
	// block; itemFree recycles slots freed by deletes. See the
	// chunk-allocator note above the struct.
	itemChunks [][]Item
	chunkUsed  int
	itemFree   []*Item
	// bytes is the running sum of approxItemSize(item) over items. Only
	// mutated under b.mu; the store-level total is kept in sync via
	// s.reserveBytes (single-item write paths) and
	// scopeBuffer.commitReplacement (bulk /warm and /rebuild).
	//
	// Note: bytes only accounts for stored Item structs + payload
	// bytes — secondary-index overhead (byID map buckets) is observability
	// noise and not charged to the store byte budget.
	bytes     int64
	createdTS int64
	// lastWriteTS is the microsecond timestamp of the most recent
	// write that touched this scope. Set under b.mu by every write
	// path; read under b.mu.RLock by stats(). Initialised equal to
	// createdTS so a freshly-created scope reports a non-zero value
	// (creation is the first "touch"). Surfaced as last_write_ts on
	// /stats; distinct from lastAccessTS, which tracks reads.
	lastWriteTS int64
	// lastAccessTS and readCountTotal are atomic so the read-hot path
	// (recordRead) stays lock-free. Taking b.mu here would serialise
	// every /get, /head and /tail hit against a single
	// scope's mutex — the dominant lock-wait source on read-heavy
	// workloads. Keep it atomic.
	lastAccessTS   atomic.Int64
	readCountTotal atomic.Uint64
}

// allocItemLocked returns a stable *Item holding src, drawn from a
// recycled freeList slot when available, otherwise from the current
// chunk (allocating a fresh, geometrically-larger block when the
// current one is full). The returned pointer is stable for the item's
// lifetime — blocks never move or realloc.
//
// PRECONDITION: caller holds b.mu (write lock).
func (b *scopeBuffer) allocItemLocked(src Item) *Item {
	if n := len(b.itemFree); n > 0 {
		p := b.itemFree[n-1]
		b.itemFree[n-1] = nil
		b.itemFree = b.itemFree[:n-1]
		*p = src
		return p
	}
	if len(b.itemChunks) == 0 || b.chunkUsed == len(b.itemChunks[len(b.itemChunks)-1]) {
		b.itemChunks = append(b.itemChunks, make([]Item, nextItemChunkSize(len(b.itemChunks))))
		b.chunkUsed = 0
	}
	last := b.itemChunks[len(b.itemChunks)-1]
	p := &last[b.chunkUsed]
	b.chunkUsed++
	*p = src
	return p
}

// freeItemLocked zeroes p (so retained string / []byte headers don't
// pin cache bytes via a dead slot) and returns its slot to the scope
// freeList for reuse by a later allocItemLocked.
//
// PRECONDITION: caller holds b.mu (write lock).
func (b *scopeBuffer) freeItemLocked(p *Item) {
	*p = Item{}
	b.itemFree = append(b.itemFree, p)
}

// itemCapacityLocked is the total Item-slot capacity across all chunks
// (used + free). PRECONDITION: caller holds b.mu.
func (b *scopeBuffer) itemCapacityLocked() int {
	n := 0
	for _, c := range b.itemChunks {
		n += len(c)
	}
	return n
}

// adoptStorageLocked installs a freshly-built replacement block
// (buildReplacementState's single backing array) as the scope's sole
// Item chunk, discarding any previous chunks — the old Items go to GC
// with them, and the freeList is cleared. Subsequent appends grow new
// chunks on top. PRECONDITION: caller holds b.mu (or the buffer is not
// yet published, as in rebuildAll's off-map construction).
func (b *scopeBuffer) adoptStorageLocked(storage []Item) {
	if len(storage) == 0 {
		b.itemChunks = nil
		b.chunkUsed = 0
	} else {
		b.itemChunks = [][]Item{storage}
		b.chunkUsed = len(storage)
	}
	b.itemFree = nil
}