Skip to content

Git designed for AI agents.

13.7 KB
Raw Blame
package cachetier

import (
	"context"
	"errors"
	"io"
	"time"

	"github.com/feder-cr/git-ai/internal/structerr"
	"github.com/feder-cr/git-ai/proto/go/gitalypb"
)

const (
	// fetchTimeout bounds one batched upstream fetch. The fetch runs detached
	// from the caller's context so that a client disconnect does not fail the
	// other requests waiting for the same objects.
	fetchTimeout = 5 * time.Minute

	// entryOverhead approximates the per-entry bookkeeping cost in bytes.
	entryOverhead = 128

	// maxPreallocBytes caps the buffer preallocated from an upstream size
	// header, so a bogus size cannot exhaust memory before data arrives.
	maxPreallocBytes = 16 << 20
)

// errOverRequestBudget reports that a request's misses exceed its byte budget.
// The request is then streamed through the upstream instead of being cached.
var errOverRequestBudget = errors.New("the misses of the request exceed its byte budget")

// requestBudget counts the object data that one GetObjects request holds
// outside the in-memory LRU: objects read from disk, objects received from the
// upstream and objects taken over from another request's fill. Objects found in
// the LRU are not counted, because MaxBytes already bounds them. A request is
// served by one goroutine, so the budget needs no locking.
type requestBudget struct {
	max  int64
	used int64
}

// remaining returns the bytes the request may still load.
func (b *requestBudget) remaining() int64 {
	return b.max - b.used
}

// charge counts n more bytes and returns errOverRequestBudget once the request
// holds more than its budget.
func (b *requestBudget) charge(n int64) error {
	b.used += n
	if b.used > b.max {
		return errOverRequestBudget
	}
	return nil
}

// objectKey identifies an object or tree within one repository.
type objectKey struct {
	storage      string
	relativePath string
	oid          string
}

type cacheKind uint8

const (
	objectKind cacheKind = iota + 1
	treeKind
)

// cacheKey identifies a cache entry. Trees are cached per request shape, since
// recursion and sizes change the listing for the same tree ID.
type cacheKey struct {
	kind         cacheKind
	objectKey    objectKey
	recursive    bool
	includeSizes bool
}

// cacheEntry is either a single object or a tree listing.
type cacheEntry struct {
	obj     *object
	entries []*gitalypb.GetTreeResponse_Entry
	size    int64
}

// flight is an in-progress load of one object shared by all requests that
// need it. done is closed once obj or err has been set.
type flight struct {
	done chan struct{}
	obj  *object
	err  error
}

// ownedFetch is an object this request is responsible for loading.
type ownedFetch struct {
	key    objectKey
	flight *flight
}

// waitingFetch is an object another request is already loading.
type waitingFetch struct {
	oid    string
	flight *flight
}

// loadObjects returns the objects for oids keyed by object ID. A missing object
// maps to nil. Objects are served from memory, then disk, then one batched
// upstream fetch. Concurrent loads of the same object are coalesced.
//
// Every object that is not served from the LRU counts against the request's
// budget of maxRequestBytes. A request that would exceed it fails with
// errOverRequestBudget before it holds more than the budget, so that the caller
// can stream it through the upstream instead.
func (s *Server) loadObjects(ctx context.Context, repo *gitalypb.Repository, oids []string) (map[string]*object, error) {
	result := make(map[string]*object, len(oids))
	budget := &requestBudget{max: s.maxRequestBytes}

	pending := oids
	for len(pending) > 0 {
		retry, err := s.loadPass(ctx, repo, pending, result, budget)
		if err != nil {
			return nil, err
		}
		pending = retry
	}

	return result, nil
}

// loadPass makes one attempt to load oids into result. It returns the object IDs
// whose coalesced load failed in another request. Those must be retried, because
// a failure of another client's fill says nothing about this request. The retry
// either finds the object in memory, owns a new fill with this request's own
// credentials, or joins a newer flight.
func (s *Server) loadPass(ctx context.Context, repo *gitalypb.Repository, oids []string, result map[string]*object, budget *requestBudget) ([]string, error) {
	var owned []ownedFetch
	var waiting []waitingFetch

	// Classification happens under one lock so that a request either owns a
	// flight or waits on one, never both. This rules out waits cycling between
	// two requests that each own what the other waits for.
	s.mu.Lock()
	for _, oid := range oids {
		key := objectKey{storage: repo.GetStorageName(), relativePath: repo.GetRelativePath(), oid: oid}

		if entry, ok := s.memory.get(cacheKey{kind: objectKind, objectKey: key}); ok {
			s.objectHits.Add(1)
			result[oid] = entry.obj
			continue
		}

		if f, ok := s.inflight[key]; ok {
			s.coalesced.Add(1)
			waiting = append(waiting, waitingFetch{oid: oid, flight: f})
			continue
		}

		s.objectMisses.Add(1)
		f := &flight{done: make(chan struct{})}
		s.inflight[key] = f
		owned = append(owned, ownedFetch{key: key, flight: f})
	}
	s.mu.Unlock()

	if len(owned) > 0 {
		loaded, err := s.fetchOwned(ctx, repo, owned, budget)
		if err != nil {
			return nil, err
		}
		for oid, obj := range loaded {
			result[oid] = obj
		}
	}

	var retry []string
	for _, w := range waiting {
		select {
		case <-w.flight.done:
		case <-ctx.Done():
			// The caller gave up, so report its own cancellation rather than
			// Unavailable. Clients that retry Unavailable would otherwise retry a
			// request the caller already abandoned.
			if errors.Is(ctx.Err(), context.DeadlineExceeded) {
				return nil, structerr.NewDeadlineExceeded("waiting for object %s: %v", w.oid, ctx.Err())
			}
			return nil, structerr.NewCanceled("waiting for object %s: %v", w.oid, ctx.Err())
		}
		if w.flight.err != nil {
			retry = append(retry, w.oid)
			continue
		}
		// The owner's request may finish and the LRU may drop the object, while
		// this request still holds it. It therefore counts against this budget too.
		if obj := w.flight.obj; obj != nil {
			if err := budget.charge(int64(len(obj.data))); err != nil {
				return nil, err
			}
		}
		result[w.oid] = w.flight.obj
	}

	return retry, nil
}

// fillContext returns the context for an upstream fill that serves the request
// carrying ctx. The fill is detached from the request's cancellation, so that
// one client's disconnect does not fail the other requests waiting for the same
// objects. It keeps the request's outgoing metadata, which is the only way its
// credentials reach the upstream.
func (s *Server) fillContext(ctx context.Context) (context.Context, error) {
	outCtx, err := s.outgoingContext(ctx)
	if err != nil {
		return nil, err
	}
	return context.WithoutCancel(outCtx), nil
}

// fetchOwned loads the objects this request owns and resolves their flights.
// Every flight is resolved before fetchOwned returns, on success and on error.
// Disk hits and upstream misses both count against budget.
func (s *Server) fetchOwned(ctx context.Context, repo *gitalypb.Repository, owned []ownedFetch, budget *requestBudget) (map[string]*object, error) {
	loaded := make(map[string]*object, len(owned))
	var remaining []ownedFetch

	for i, o := range owned {
		if s.disk != nil {
			// The size is checked against the budget before the object is
			// allocated, so a request cannot buffer more than its budget of
			// objects that only the disk store holds.
			obj, err := s.disk.read(o.key, budget.remaining())
			if obj != nil {
				err = budget.charge(int64(len(obj.data)))
			}
			if errors.Is(err, errObjectOverLimit) || errors.Is(err, errOverRequestBudget) {
				// Release the flights that were not loaded, so that their waiters
				// retry with their own budgets.
				for _, rest := range append(remaining, owned[i:]...) {
					s.resolve(rest, nil, errOverRequestBudget)
				}
				return nil, errOverRequestBudget
			}
			if err != nil {
				s.logger.WithError(err).WithField("oid", o.key.oid).Warn("graft-cache: read object from disk")
			}
			if obj != nil {
				s.diskHits.Add(1)
				s.store(o.key, obj, false)
				loaded[o.key.oid] = obj
				s.resolve(o, obj, nil)
				continue
			}
		}
		remaining = append(remaining, o)
	}

	if len(remaining) == 0 {
		return loaded, nil
	}

	oids := make([]string, 0, len(remaining))
	for _, o := range remaining {
		oids = append(oids, o.key.oid)
	}

	base, err := s.fillContext(ctx)
	if err != nil {
		for _, o := range remaining {
			s.resolve(o, nil, err)
		}
		return nil, err
	}

	fetchCtx, cancel := context.WithTimeout(base, fetchTimeout)
	defer cancel()

	fetched, err := s.fetchFromUpstream(fetchCtx, repo, oids, budget)
	if err != nil {
		for _, o := range remaining {
			s.resolve(o, nil, err)
		}
		return nil, err
	}

	for _, o := range remaining {
		obj := fetched[o.key.oid]
		if obj != nil {
			s.store(o.key, obj, true)
			loaded[o.key.oid] = obj
		}
		s.resolve(o, obj, nil)
	}

	return loaded, nil
}

// resolve publishes the outcome of an owned fetch and wakes all waiters.
func (s *Server) resolve(o ownedFetch, obj *object, err error) {
	s.mu.Lock()
	if s.inflight[o.key] == o.flight {
		delete(s.inflight, o.key)
	}
	s.mu.Unlock()

	o.flight.obj = obj
	o.flight.err = err
	close(o.flight.done)
}

// store puts a verified object into memory and, if requested and configured,
// onto disk. Disk failures are logged and never fail the request.
func (s *Server) store(key objectKey, obj *object, toDisk bool) {
	// The entry keeps the whole backing array alive, so its capacity is what counts
	// against the memory budget.
	s.memory.add(cacheKey{kind: objectKind, objectKey: key}, &cacheEntry{obj: obj, size: int64(cap(obj.data)) + entryOverhead})

	if toDisk && s.disk != nil {
		if err := s.disk.write(key, obj); err != nil {
			s.logger.WithError(err).WithField("oid", key.oid).Warn("graft-cache: write object to disk")
		}
	}
}

// fetchFromUpstream loads oids with one GetObjects call and verifies every
// object it receives. Missing objects are returned as nil entries. The data it
// receives counts against budget.
func (s *Server) fetchFromUpstream(ctx context.Context, repo *gitalypb.Repository, oids []string, budget *requestBudget) (map[string]*object, error) {
	stream, err := s.upstream.GetObjects(ctx, &gitalypb.GetObjectsRequest{
		Repository: repo,
		Oids:       oids,
	})
	if err != nil {
		return nil, err
	}

	requested := make(map[string]bool, len(oids))
	for _, oid := range oids {
		requested[oid] = true
	}

	result := make(map[string]*object, len(oids))

	var cur *partialObject
	finish := func() error {
		if cur == nil {
			return nil
		}
		p := cur
		cur = nil

		if int64(len(p.obj.data)) != p.size {
			return structerr.NewDataLoss("upstream object %s: got %d of %d bytes", p.oid, len(p.obj.data), p.size)
		}
		if err := verifyObject(p.oid, p.obj); err != nil {
			s.verifyFailures.Add(1)
			return structerr.NewDataLoss("upstream object %s: %v", p.oid, err)
		}
		result[p.oid] = p.obj
		return nil
	}

	for {
		msg, err := stream.Recv()
		if errors.Is(err, io.EOF) {
			break
		}
		if err != nil {
			return nil, err
		}

		if cur != nil && msg.GetOid() != cur.oid {
			if err := finish(); err != nil {
				return nil, err
			}
		}

		oid := msg.GetOid()
		if !requested[oid] {
			return nil, structerr.NewInternal("upstream returned unrequested object %q", oid)
		}
		if _, seen := result[oid]; seen {
			return nil, structerr.NewInternal("upstream returned object %s twice", oid)
		}

		if msg.GetMissing() {
			result[oid] = nil
			continue
		}

		if cur == nil {
			if msg.GetOffset() != 0 {
				return nil, structerr.NewInternal("upstream object %s starts at offset %d", oid, msg.GetOffset())
			}
			if msg.GetSize() < 0 {
				return nil, structerr.NewInternal("upstream object %s has negative size", oid)
			}
			if _, ok := typeName(msg.GetType()); !ok {
				return nil, structerr.NewInternal("upstream object %s has unsupported type %v", oid, msg.GetType())
			}
			prealloc := msg.GetSize()
			if prealloc > maxPreallocBytes {
				prealloc = maxPreallocBytes
			}
			cur = &partialObject{
				oid:  oid,
				size: msg.GetSize(),
				obj:  &object{typ: msg.GetType(), data: make([]byte, 0, prealloc)},
			}
		}

		if msg.GetOffset() != int64(len(cur.obj.data)) {
			return nil, structerr.NewInternal("upstream object %s: chunk at offset %d, expected %d", oid, msg.GetOffset(), len(cur.obj.data))
		}
		if int64(len(cur.obj.data))+int64(len(msg.GetData())) > cur.size {
			return nil, structerr.NewInternal("upstream object %s: more data than its declared size", oid)
		}
		// The budget spans all objects of the request, including those read from
		// disk, so that the request's memory stays within maxRequestBytes.
		if err := budget.charge(int64(len(msg.GetData()))); err != nil {
			return nil, err
		}
		cur.obj.data = appendBounded(cur.obj.data, msg.GetData(), cur.size)
	}

	if err := finish(); err != nil {
		return nil, err
	}

	for _, oid := range oids {
		if _, ok := result[oid]; !ok {
			return nil, structerr.NewInternal("upstream did not return object %s", oid)
		}
	}

	return result, nil
}

// appendBounded appends chunk to data like append, but never grows the capacity
// beyond limit, the declared size of the object. append's growth policy would leave
// the backing array of a large object up to ~25% larger than its content, memory
// that the cache keeps alive without accounting for it. A complete object, whose
// length equals its declared size, therefore has no spare capacity. The caller
// guarantees that len(data)+len(chunk) <= limit.
func appendBounded(data, chunk []byte, limit int64) []byte {
	need := len(data) + len(chunk)
	if need <= cap(data) {
		return append(data, chunk...)
	}

	newCap := int64(max(2*cap(data), need))
	if newCap > limit {
		newCap = limit
	}

	grown := make([]byte, len(data), newCap)
	copy(grown, data)
	return append(grown, chunk...)
}

// partialObject is an object whose chunks are still being received.
type partialObject struct {
	oid  string
	size int64
	obj  *object
}