Skip to content
go-libfossil Artifact [63e8211f13]
Login

Artifact [63e8211f13]

Check-ins Using Download Hex

Artifact 63e8211f1303f5e9ded0278216931f45db528c5a683a158849500144fbc1ab08:

package content

import (
	"database/sql"
	"errors"
	"fmt"

	"github.com/danmestas/go-libfossil/db"
	libfossil "github.com/danmestas/go-libfossil/internal/fsltype"
)

// maxDeltaChainDepth bounds every delta-chain walk in the package: the two
// read-path walks, IsAvailable here and walkDeltaChain in content.go, and the
// write-path walk deltifyBreaksLoop in deltify.go. Each stops after visiting
// this many nodes. One concept, one bound: the rationale below is the same for
// all three, since they walk the same delta table over the same chains.
//
// A chain cannot be longer than the number of stored versions of one file.
// The deepest chain in the Fossil SCM repository, the largest corpus this
// package is measured against, is 2,546 nodes; the average is 469. This bound
// is roughly six times the observed maximum, so a chain that reaches it is
// corrupt or hostile rather than merely large. Reaching it is a safe failure:
// IsAvailable reports the content unavailable, which defers the artifact, and
// walkDeltaChain returns an error rather than a partial chain.
//
// The bound is a backstop, not the defence. Termination on a cyclic delta
// table — reachable from a corrupt repository, or from a peer that plants one
// during clone — comes from the visited-set check in each walk, which stops at
// the first repeat. Without that, this constant is the number of queries an
// attacker buys per call, and both walks are wire-reachable: IsAvailable runs
// once per F-card of every check-in being crosslinked.
const maxDeltaChainDepth = 16_384

// IsAvailable reports whether the content of rid can actually be read.
//
// This is the availability predicate, distinct from blob.Exists, which
// answers only whether a row is present. It returns false for a phantom
// (blob.size < 0), false for an unknown rid, and — transitively — false for a
// delta whose chain bottoms out in a phantom, even though every blob row in
// that chain exists. It returns true only when the full chain is grounded in
// readable full-text content.
//
// Ported from Fossil's content_is_available (src/content.c:163). Callers must
// never walk the delta table themselves; that logic lives here alone.
func IsAvailable(q db.Querier, rid libfossil.FslID) bool {
	if q == nil {
		panic("content.IsAvailable: q must not be nil")
	}
	available, err := checkAvailable(q, rid)
	if err != nil {
		return false // A fault reads as unavailable; CheckAvailableByUUID reports it.
	}
	return available
}

// checkAvailable is IsAvailable's walk, reporting a database fault as an
// error instead of as "unavailable". An unknown rid, a phantom, a cycle or an
// over-long chain is a plain false.
func checkAvailable(q db.Querier, rid libfossil.FslID) (bool, error) {
	if q == nil {
		panic("content.checkAvailable: q must not be nil")
	}
	if rid <= 0 {
		return false, nil
	}

	// One statement per chain node, not two. Every SQL round trip here pays
	// a WAL read-lock acquisition, and this walk runs once per F-card of
	// every check-in being crosslinked, over chains that are thousands of
	// nodes deep in a real repository — the round trips, not the work they
	// do, are the cost.
	const step = `SELECT b.size, d.rid IS NOT NULL, d.srcid
	                FROM blob b LEFT JOIN delta d ON d.rid = b.rid
	               WHERE b.rid = ?`

	// A cycle ends the walk at the first repeat rather than at
	// maxDeltaChainDepth. The difference is what a peer who plants a
	// two-node cycle costs us: two queries instead of the bound.
	seen := make(map[libfossil.FslID]struct{})

	current := rid
	for depth := 0; depth < maxDeltaChainDepth; depth++ {
		if _, repeat := seen[current]; repeat {
			return false, nil // cycle — the chain is not grounded in anything
		}
		seen[current] = struct{}{}

		var size sql.NullInt64
		var hasDelta bool
		var srcid sql.NullInt64
		err := q.QueryRow(step, current).Scan(&size, &hasDelta, &srcid)
		if errors.Is(err, sql.ErrNoRows) {
			return false, nil // unknown rid
		}
		if err != nil {
			return false, fmt.Errorf("content: availability of rid %d: %w", current, err)
		}
		if !size.Valid || size.Int64 < 0 {
			return false, nil // phantom (a NULL size, legal in the schema, too)
		}
		if !hasDelta {
			return true, nil // chain is grounded in full-text content
		}
		// delta.srcid is NOT NULL in the schema, so Valid is always true
		// here. Checking it costs nothing and keeps a schema change from
		// turning into a NULL scanned as zero, which reads as "grounded".
		if !srcid.Valid {
			return false, nil
		}
		if srcid.Int64 == 0 {
			return true, nil
		}
		current = libfossil.FslID(srcid.Int64)
	}
	return false, nil // bound exceeded — pathological chain
}

// AvailableByUUID resolves uuid to its rid and reports whether that
// artifact's content is available, per IsAvailable. A database fault reads as
// unavailable; a caller that tolerates missing content on purpose must use
// CheckAvailableByUUID, so a fault is not mistaken for it.
//
// Use this in place of blob.Exists wherever the resolved rid is about to be
// passed to Expand: blob.Exists answers true for a phantom, whose content
// cannot be read.
func AvailableByUUID(q db.Querier, uuid string) (libfossil.FslID, bool) {
	rid, available, err := CheckAvailableByUUID(q, uuid)
	if err != nil {
		return 0, false
	}
	return rid, available
}

// CheckAvailableByUUID is AvailableByUUID that reports a database fault as an
// error, distinct from content that is simply not there (an unknown uuid, a
// phantom, or a delta on one), which is (0, false, nil).
func CheckAvailableByUUID(q db.Querier, uuid string) (libfossil.FslID, bool, error) {
	if q == nil {
		panic("content.CheckAvailableByUUID: q must not be nil")
	}
	if uuid == "" {
		panic("content.CheckAvailableByUUID: uuid must not be empty")
	}

	var rid int64
	err := q.QueryRow("SELECT rid FROM blob WHERE uuid=?", uuid).Scan(&rid)
	if errors.Is(err, sql.ErrNoRows) {
		return 0, false, nil
	}
	if err != nil {
		return 0, false, fmt.Errorf("content: look up %s: %w", uuid, err)
	}
	available, err := checkAvailable(q, libfossil.FslID(rid))
	if err != nil {
		return 0, false, err
	}
	if !available {
		return 0, false, nil
	}
	return libfossil.FslID(rid), true, nil
}

// AvailabilityCache memoizes IsAvailable across many calls that share delta
// chains, for a caller that knows blob content is immutable for the cache's
// lifetime -- a single crosslink sweep. IsAvailable walks a blob's whole delta
// chain on every call, and crosslink calls it once per F-card of every
// check-in, so the same file blobs -- and the same chain suffixes -- are walked
// again and again; on the Fossil SCM corpus that walk was ~40% of the sweep.
//
// A blob's availability is a property of its chain, and every node above a
// given node in the same chain shares that node's grounding or phantom, so one
// walk decides every node it passes through. The cache records that verdict for
// each rid, and a later walk that reaches an already-decided rid stops there.
// Total walk work over a sweep is then bounded by the number of distinct blobs,
// not by the number of F-card references.
//
// ByUUID additionally memoizes the uuid->rid resolution the walk starts from.
// That lookup, not the walk, is what a sweep repeats: every F-card of every
// check-in names a file by hash, the same file hash appears in every revision
// that did not change it, and each name costs an index seek into a blob.uuid
// index far larger than SQLite's page cache. On the Fossil SCM repository that
// one statement was 27% of a whole clone's CPU -- more than delta expansion,
// hash verification and the receive path combined -- while the chain walk it
// guards was under 1%.
//
// # Scope
//
// Not safe for concurrent use. Both memos below are sound because of where
// this type is used, not because the facts they hold are permanent, so the
// scope is the invariant and it is worth stating exactly.
//
// A cache belongs to ONE crosslink run: one whole-repository sweep
// (manifest.linkCandidatesInOrder) or one phantom-fill cascade
// (manifest.newCascadeLinker). Both build it as a local, neither hands it to a
// *repo.Repo or keeps it past the call, and nothing else constructs one. Over
// that window blob rows are only ever added -- crosslinking creates phantoms,
// fills them, and rewrites how content is stored, but removes nothing.
//
// The one operation in the tree that removes a blob row is shun.Purge, which
// DELETEs from blob and delta. It has no production caller today; it runs as
// its own top-level operation, not from inside a sweep or a sync round. If
// that ever changes -- a sync learning to process shun cards mid-round is the
// plausible way -- a cache must not span it, because a memoized rid would then
// name a row that no longer exists. See
// TestAvailabilityCacheMustNotSpanAPurge, which pins that consequence so it is
// discovered by a failing test rather than by a wrong derivation.
//
// Widening the lifetime past one crosslink run -- caching one per repository,
// or per process -- reopens exactly that question and is not a free change.
type AvailabilityCache struct {
	avail map[libfossil.FslID]bool
	// rids memoizes uuid -> rid for hashes that resolved to a blob row.
	//
	// Only successful resolutions are recorded, and that asymmetry is
	// load-bearing rather than an omission. Within the scope above a uuid that
	// names a row keeps naming the same row: blob.uuid is UNIQUE, rids are
	// never reassigned, and nothing a crosslink run does deletes the row. A
	// uuid that names NO row can gain one at any moment -- ridOrPhantom and
	// blob.StorePhantom both create rows mid-run -- so caching the absence
	// would answer a later question with an earlier repository, and an
	// artifact would stay deferred after the content it waits on arrived. The
	// negative case is also the rare one: it means an artifact references
	// content that has not arrived, which is the exception a sweep defers on,
	// not the rule it runs on.
	rids map[string]libfossil.FslID
}

// NewAvailabilityCache returns an empty availability cache.
func NewAvailabilityCache() *AvailabilityCache {
	return &AvailabilityCache{
		avail: make(map[libfossil.FslID]bool),
		rids:  make(map[string]libfossil.FslID),
	}
}

// ByUUID resolves uuid to its rid and reports whether that blob's content is
// available, memoizing the chain walk. Semantics match AvailableByUUID.
func (a *AvailabilityCache) ByUUID(q db.Querier, uuid string) (libfossil.FslID, bool) {
	if a == nil {
		return AvailableByUUID(q, uuid)
	}
	if q == nil {
		panic("content.AvailabilityCache.ByUUID: q must not be nil")
	}
	if uuid == "" {
		panic("content.AvailabilityCache.ByUUID: uuid must not be empty")
	}

	rid, ok := a.ridForUUID(q, uuid)
	if !ok {
		return 0, false
	}
	if !a.isAvailable(q, rid) {
		return 0, false
	}
	return rid, true
}

// ridForUUID resolves uuid to its blob rid, memoizing hits. See the note on
// AvailabilityCache.rids for why misses are deliberately not memoized.
func (a *AvailabilityCache) ridForUUID(q db.Querier, uuid string) (libfossil.FslID, bool) {
	if rid, ok := a.rids[uuid]; ok {
		return rid, true
	}
	var rid int64
	if err := q.QueryRow("SELECT rid FROM blob WHERE uuid=?", uuid).Scan(&rid); err != nil {
		return 0, false
	}
	a.rids[uuid] = libfossil.FslID(rid)
	return libfossil.FslID(rid), true
}

// isAvailable is IsAvailable with memoization. It walks rid's chain until it
// reaches a node whose verdict is already cached, a phantom or unknown rid
// (unavailable), a grounded full-text root (available), a cycle (unavailable),
// or the depth bound (unavailable) -- then records that one verdict for every
// node it walked, since they all share it.
func (a *AvailabilityCache) isAvailable(q db.Querier, rid libfossil.FslID) bool {
	if rid <= 0 {
		return false
	}
	if v, ok := a.avail[rid]; ok {
		return v
	}

	const step = `SELECT b.size, d.rid IS NOT NULL, d.srcid
	                FROM blob b LEFT JOIN delta d ON d.rid = b.rid
	               WHERE b.rid = ?`

	// walked holds every node whose verdict this call decides; result is the
	// verdict they share. seen catches a cycle within this walk (nodes already
	// cached are handled by the memo check and never re-entered).
	var walked []libfossil.FslID
	seen := make(map[libfossil.FslID]struct{})
	result := false
	faulted := false
	current := rid
	for depth := 0; depth < maxDeltaChainDepth; depth++ {
		if v, ok := a.avail[current]; ok {
			result = v
			break
		}
		if _, repeat := seen[current]; repeat {
			result = false // cycle — not grounded in anything
			break
		}
		seen[current] = struct{}{}
		walked = append(walked, current)

		var size sql.NullInt64
		var hasDelta bool
		var srcid sql.NullInt64
		if err := q.QueryRow(step, current).Scan(&size, &hasDelta, &srcid); err != nil {
			// An unknown rid is a verdict; a fault is not, so it is not
			// remembered for the rest of the sweep.
			faulted = !errors.Is(err, sql.ErrNoRows)
			result = false
			break
		}
		if !size.Valid || size.Int64 < 0 {
			result = false // phantom (a NULL size too)
			break
		}
		if !hasDelta {
			result = true // chain is grounded in full-text content
			break
		}
		if !srcid.Valid {
			result = false // schema guard: a NULL srcid must not read as grounded
			break
		}
		if srcid.Int64 == 0 {
			result = true // grounded
			break
		}
		current = libfossil.FslID(srcid.Int64)
	}

	if faulted {
		return false
	}
	for _, n := range walked {
		a.avail[n] = result
	}
	return result
}