Artifact [d013db9538]

Artifact d013db9538de0aa50c3e24f3b086a8310950e37c9540765aa626f30525be5377:

• File internal/content/chain_bound_test.go — part of check-in [9864120a32] at 2026-07-20 02:36:37 on branch trunk — perf: memoize delta-chain interiors during crosslink (#107)

  * perf: memoize delta-chain interiors during crosslink (#89)

  manifest.Crosslink ran at roughly 1.4 events/sec on the Fossil SCM repository, which puts a 27,000-artifact clone at two and a half hours of CPU after the transfer has already finished. A CPU profile of a sweep over that corpus attributes 152.77s of Crosslink's 167.20s -- 91% -- to content.Expand, and 126.35s of that to the single blob.Load inside its delta-replay loop.

  The cause is chain depth, not per-event overhead: not a transaction per event, not a missing index, not a full-table scan. content_deltify stores a file's older versions as deltas against its newer ones, so one file's history is a single chain -- 469 nodes deep on average across that repository, 1,032 for the blobs carrying artifacts, 2,546 at worst. Expand walked each chain from its root on every call and Crosslink calls it once per blob, so the sweep performed 31.7 million delta applications to expand 67,451 blobs.

  Cache.Expand now stops the chain walk at the deepest ancestor it already holds and keeps every node it materializes on the way forward, and Crosslink runs one such cache for the sweep. Blob content is immutable once written and the candidate rids are snapshotted before the loop, so nothing a sweep does can invalidate an entry.

  Every node handed to the cache is verified against the UUID its blob row is stored under before it is stored, because a cached interior is served later as if it had been expanded in its own right. The number of hash checks per sweep does not change: each blob is materialized once and verified once, where before each was expanded once and verified once. A plain Expand, with no cache, walks and verifies exactly as it did.

  IsAvailable folds its two-statements-per-chain-node walk into one. It runs once per F-card of every check-in being crosslinked, over the same deep chains, and every SQL round trip there pays a WAL read-lock acquisition -- the round trips, not the work they do, are the cost.

  No transaction boundary moves and no batching is introduced. A manifest that fails to crosslink still fails on its own, exactly where it did.

  Measured on the Fossil SCM repository, 67,451 content blobs and 27,060 artifacts. Time for Crosslink to write its first 300 event rows: 221s before, 131s after. Over the expansion path in isolation, sweeping the same corpus in rid order: 22.9 blobs/sec with no cache, 50.1 at the 256 MiB budget set here, 414 at 1 GiB -- where the process needs 2.9 GB resident, which is why 1 GiB is not the number.

  A bounded cache cannot close the gap on its own. Chains run from a high-rid root down to low-rid ancestors while the sweep visits rids ascending, so the first candidate of a chain materializes all of it and the remaining nodes are consumed arbitrarily far in the future; the working set of a whole-repository sweep in rid order is the whole repository expanded, 8 GiB for this corpus. Closing it means visiting candidates in delta-chain order, which is how Fossil's own rebuild avoids the cost, and which changes the order-sensitive state Crosslink writes -- leaf, tag propagation, tech-note event replacement, forum thread titles. That is a separate change.

  TestFossilBinaryReadsCrosslinkedRepo covers the acceptance criterion this cannot self-certify: a repository whose relational tables were written through the accelerated path passes fossil 2.28's test-integrity, shows its tip in fossil timeline, survives fossil rebuild, and its event, plink, leaf and mlink rows match, column for column, what fossil derives from the same blobs.

  * fix: bound and cycle-check the delta-chain walks (#89)

  IsAvailable walked the delta chain with no cycle detection, to a bound of 100,000 against real chains whose deepest observed node count is 2,546. It is wire-reachable -- sync/clone.go, sync/handler.go, and once per F-card of every check-in Crosslink processes -- so a peer that plants a two-node delta cycle bought a 100,000-iteration query loop on every call, inside whatever process embeds this library.

  Both halves are fixed. Each walk now carries a visited set and stops at the first repeat, which is the actual defence: a cycle costs its own length, not the bound. maxDeltaChainDepth replaces the old constant at 16,384, roughly six times the deepest chain measured on the Fossil SCM repository, and it is now a backstop for an acyclic-but-absurd chain rather than a number an attacker spends. walkDeltaChain, which the memoizing expansion path made hotter, previously had no bound at all and now shares the same one.

  This is what made TestIsAvailable_CyclicChainTerminates sit at ~99% of its 30s budget on main and fail outright under -race here: the cyclic walk was running the full bound. It now finishes in about a second under -race, six runs out of six.

  walkDeltaChain returns the content it stopped on instead of leaving expandChain to ask the store a second time. The truncation decision and the use of it were separate steps, so a concurrent eviction between them would send a delta row to blob.Load and hand raw delta bytes to the replay as full text. bindToName caught that and failed closed, but the caller saw a hash mismatch on an artifact that was not corrupt, and Crosslink's error path drops those silently. Unreachable while the cache is a single-goroutine local, but Cache is documented concurrency-safe and takes its mutex on every method, so the type promised something the expansion path did not deliver.

  Cache entries are clipped to their length before being stored, so curSize is the bytes actually retained rather than an allocator-dependent approximation of them.

  Test corrections: the corpus harness no longer closes the repository handle out from under the sweep goroutine when it returns at the event target; the sweep owns the handle and closes it. snapshotDerived now fails on an empty digest rather than comparing "" to "" and passing without examining a row. The fail-closed injector matches the merged chain-step statement specifically rather than any query mentioning delta, and says what it can and cannot prove now that the two lookups are one statement. The fossilbin comparison documents that it is not full-table equivalence, and which tables it leaves uncompared.

  MEASUREMENTS, SUPERSEDING THOSE IN 2426591

  The figures in the parent commit were taken before clipping, and its "221s -> 131s" pair predates the double-hash and IsAvailable fixes that landed in that same commit. Everything below was re-measured on the code as it ships, one run at a time on an idle machine, against the Fossil SCM repository (67,451 content blobs, 27,060 artifacts).

  Crosslink to its first 300 event rows, cpuprofile on throughout:

  original code 221.4s as shipped 103.9s 2.1x

  Expanding the first 4,000 blobs, which isolates the expansion path:

  budget throughput peak RSS entries held none 22.1 blobs/s 169 MB 0 0 256 MiB 52.0 blobs/s 1036 MB 543 255 MiB 1 GiB 468.3 blobs/s 2278 MB 15,842 1021 MiB

  Clipping changed neither throughput nor memory. Crosslink to 300 events runs 103.9s clipped against 105.9s unclipped, peak RSS 1067 MB against 1050 MB, and the cache holds the identical 543 entries and 255 MiB at a 256 MiB budget either way -- at these sizes the buffers already arrive tightly sized. It is worth keeping as an accounting guarantee, not as a saving, and the comment on clip says so.

  The earlier claim that capacity slack was why a 256 MiB cache reached nearly a gigabyte resident was wrong. Peak RSS tracks the no-cache baseline plus roughly twice the budget, because the cache is live data and the collector sizes the heap against it: 169 + 2x1021 = 2211 against 2278 observed at 1 GiB. That is why the budget stays at 256 MiB -- a gigabyte of cache costs over two gigabytes resident to clone a 72 MB repository. The shape of the curve did not move.

  * docs: correct the claims around the chain bound and the RSS model (#89)

  Three claims did not survive checking, and one bound was a node out.

  maxDeltaChainDepth said it bounds "every delta-chain walk in this package". It does not: deltifyBreaksLoop is a third walk, under deltifyMaxChainWalk, which is 64 times larger. The rationale on the new constant applies to that walk just as well, but changing it would change deltify's shipped behaviour, so the sentence is narrowed to the two read-path walks it actually governs and points at the third rather than quietly covering it.

  Two comments still named maxAvailabilityChainDepth, which no longer exists, and argued from IsAvailable having a bound "of its own" -- the framing of a world where the two walks had separate bounds. Against a shared constant that argument reads backwards. Both now name the shared bound, and the reason deltifyBreaksLoop keeps its own visited set and its own step cap is stated as the general rule it is: every walk over the peer-shaped delta graph carries both, and none of them relies on another walk's guard.

  The retraction in the previous commit replaced one unsupported mechanism with another. "Peak RSS runs at roughly the baseline plus twice the budget" is a two-point fit whose worse point is the shipped one: it is 3% off at 1 GiB and 53% under at 256 MiB, where resident memory is four times the budget rather than twice. The measured table stays; the model is demoted to the direction the data supports, that peak RSS grows faster than the budget, with the fit's own weakness stated.

  walkDeltaChain counted loop iterations where IsAvailable counts nodes visited, so the shared bound bit a node apart: a chain of exactly maxDeltaChainDepth+1 was unavailable to one walk and complete to the other. It now counts nodes, and TestChainBoundBitesAtSameLength pins the agreement at both boundaries -- nothing else ties the two loops together. (user: [email protected], size: 2023) [annotate] [blame] [check-ins using]

package content

import (
	"testing"

	libfossil "github.com/danmestas/libfossil/internal/fsltype"
	_ "github.com/danmestas/libfossil/internal/testdriver"
)

// maxDeltaChainDepth's doc says both read-path walks stop after visiting that
// many nodes. They reached the bound a node apart until the loop in
// walkDeltaChain was rewritten to count nodes rather than iterations, which
// meant a chain of exactly maxDeltaChainDepth+1 was unavailable to one walk
// and complete to the other. Nothing else pins the two together: each has its
// own loop, and a future edit to either can reintroduce the skew silently.
func TestChainBoundBitesAtSameLength(t *testing.T) {
	for _, n := range []int{maxDeltaChainDepth, maxDeltaChainDepth + 1} {
		d := setupTestDB(t)

		rids := make([]libfossil.FslID, n)
		for i := 0; i < n; i++ {
			res, err := d.Exec(
				"INSERT INTO blob(uuid, size, content, rcvid) VALUES(printf('%040d', ?), 42, x'00', 1)", i)
			if err != nil {
				t.Fatalf("insert blob %d: %v", i, err)
			}
			id, err := res.LastInsertId()
			if err != nil {
				t.Fatalf("LastInsertId: %v", err)
			}
			rids[i] = libfossil.FslID(id)
		}
		// An acyclic chain grounded at its far end, so only the bound can
		// decide the outcome.
		for i := 0; i < n-1; i++ {
			if _, err := d.Exec("INSERT INTO delta(rid, srcid) VALUES(?, ?)", rids[i], rids[i+1]); err != nil {
				t.Fatalf("insert delta %d: %v", i, err)
			}
		}

		available := IsAvailable(d, rids[0])
		_, _, err := walkDeltaChain(d, rids[0], nil)
		walked := err == nil

		if available != walked {
			t.Errorf("chain of %d nodes: IsAvailable=%v but walkDeltaChain succeeded=%v; "+
				"the two walks must reach maxDeltaChainDepth (%d) at the same length",
				n, available, walked, maxDeltaChainDepth)
		}
		if n == maxDeltaChainDepth && !available {
			t.Errorf("chain of exactly maxDeltaChainDepth (%d) nodes was rejected", n)
		}
		if n == maxDeltaChainDepth+1 && available {
			t.Errorf("chain of maxDeltaChainDepth+1 (%d) nodes was accepted", n)
		}
	}
}