Skip to content
go-libfossil Artifact [9ade0976ce]
Login

Artifact [9ade0976ce]

Check-ins Using Download Hex

Artifact 9ade0976ce6d6d5f63fa438011b9796a5312e98d5d8fef6d6137d2b12b9e0a52:

package delta

import (
	"bytes"
	"runtime"
	"testing"
)

func TestApply_InsertOnly(t *testing.T) {
	source := []byte{}
	target := []byte("hello")
	cs := Checksum(target)
	delta := encodeDelta(uint64(len(target)), nil, target, cs)

	got, err := Apply(source, delta)
	if err != nil {
		t.Fatalf("Apply: %v", err)
	}
	if !bytes.Equal(got, target) {
		t.Fatalf("Apply = %q, want %q", got, target)
	}
}

func TestApply_CopyFromSource(t *testing.T) {
	source := []byte("hello world")
	target := []byte("hello Go")
	cs := Checksum(target)
	delta := manualDelta(uint64(len(target)), []deltaOp{
		{opType: '@', offset: 0, length: 6},
		{opType: ':', data: []byte("Go")},
	}, cs)

	got, err := Apply(source, delta)
	if err != nil {
		t.Fatalf("Apply: %v", err)
	}
	if !bytes.Equal(got, target) {
		t.Fatalf("Apply = %q, want %q", got, target)
	}
}

// TestApply_TinyPayloadHugeHeaderBoundsAllocation is a regression test for
// a durable, remotely-planted memory-exhaustion landmine. A malicious
// delta can declare an enormous target length in its header while
// supplying almost no actual delta bytes. Before this fix, output was
// preallocated directly from that claim (make([]byte, 0, targetLen)), so
// a handful of wire bytes could trigger an allocation scaled to whatever
// the header claimed, up to maxDeltaTargetSize (4 GiB). Because a delta
// can now be stored unverified (see blob.StoreDeltaRaw), a hostile peer
// plants this once and every later Expand of that row repeats the
// attempt -- not a one-off parse spike.
//
// This claims a 100 MiB target from a payload with no command bytes
// after the header (so Apply must still fail with "missing terminator" --
// correctness is unchanged), and asserts the actual allocation growth
// stays orders of magnitude below the claim: proof the allocation is
// bounded by a fixed cap, not by the wire-supplied number.
func TestApply_TinyPayloadHugeHeaderBoundsAllocation(t *testing.T) {
	const hugeTarget = 100 << 20 // 100 MiB, comfortably under maxDeltaTargetSize
	// The header's integer is encoded in Fossil's own base-64 alphabet
	// (see appendInt), not decimal -- fmt.Sprintf("%d", ...) would
	// produce a string that happens to still parse (digits '0'-'9' are
	// valid base-64 digits in this scheme) but as a wildly different,
	// much larger value, which would be rejected by parseTargetLen's
	// maxDeltaTargetSize bound before ever reaching the allocation this
	// test targets. appendInt is the same encoder Create uses.
	header := appendInt(nil, hugeTarget)
	header = append(header, '\n')

	// Sanity: confirm the header round-trips to the value this test
	// actually intends to claim, so a future encoding change can't
	// silently turn this back into a no-op the way the decimal version did.
	got, err := OutputSize(header)
	if err != nil || got != hugeTarget {
		t.Fatalf("fixture bug: header round-trips to (%d, %v), want (%d, nil)", got, err, uint64(hugeTarget))
	}

	runtime.GC()
	var before, after runtime.MemStats
	runtime.ReadMemStats(&before)

	_, err = Apply([]byte{}, header)

	runtime.ReadMemStats(&after)

	if err == nil {
		t.Fatal("expected an error (missing terminator): header has no command bytes")
	}

	grown := after.TotalAlloc - before.TotalAlloc
	const maxSaneGrowth = 4 << 20 // 4 MiB: generous headroom over the 64 KiB cap
	if grown > maxSaneGrowth {
		t.Fatalf("Apply allocated %d bytes for a %d-byte header claiming a %d-byte target -- "+
			"want the allocation bounded by actual work performed, not by the wire-supplied claim",
			grown, len(header), hugeTarget)
	}
}

// largeTargetManyCopiesDelta builds a delta for a 1 MiB target made of
// numChunks small copy commands, each pulling chunkSize bytes straight back
// out of source at the matching offset (source and target share content, so
// the copies reconstruct target exactly). This is the shape that actually
// exercises the #81 regression: many small commands means many small
// append growth steps, which is where append's own ~1.25x large-slice
// growth factor compounds into ~5x cumulative allocation. A single big
// insert/copy command (e.g. what Create emits for two nearly-disjoint
// buffers) grows in one step and allocates ~1x on both the buggy and fixed
// code -- it does not exercise this bug at all.
func largeTargetManyCopiesDelta(t testing.TB) (source, target, d []byte) {
	t.Helper()
	const targetSize = 1 << 20 // 1 MiB, comfortably past the 64 KiB initial cap
	const chunkSize = 256
	const numChunks = targetSize / chunkSize // 4096 copy commands

	target = make([]byte, targetSize)
	for i := range target {
		target[i] = byte('a' + i%26)
	}
	source = target // copies read back the same bytes at the same offsets

	ops := make([]deltaOp, 0, numChunks)
	for i := 0; i < numChunks; i++ {
		ops = append(ops, deltaOp{opType: '@', offset: uint64(i * chunkSize), length: chunkSize})
	}
	d = manualDelta(targetSize, ops, Checksum(target))
	return source, target, d
}

// TestApply_LargeTargetAllocationBounded is a regression test for #81: for
// targets over the 64 KiB initial cap, Apply used to climb to the target
// size purely via append's own ~1.25x large-slice growth factor, which
// lands near 5x the final output size in cumulative allocation rather than
// the ~1x an exact preallocation would give. This builds a delta made of
// many small copy commands (see largeTargetManyCopiesDelta) -- the shape
// that actually compounds append's growth factor -- for a target well past
// the initial cap, and asserts total allocation growth stays within a
// small constant factor of the target size -- proof the two-stage cap
// (64 KiB, then a len(delta)-informed upgrade) is actually restoring
// near-exact sizing, not just not-regressing further.
func TestApply_LargeTargetAllocationBounded(t *testing.T) {
	const targetSize = 1 << 20 // 1 MiB
	source, target, d := largeTargetManyCopiesDelta(t)

	runtime.GC()
	var before, after runtime.MemStats
	runtime.ReadMemStats(&before)

	got, err := Apply(source, d)

	runtime.ReadMemStats(&after)

	if err != nil {
		t.Fatalf("Apply: %v", err)
	}
	if !bytes.Equal(got, target) {
		t.Fatal("round-trip failed")
	}

	grown := after.TotalAlloc - before.TotalAlloc
	// Generous headroom over 1x: covers the delta buffer itself and
	// Apply's own bounded capacity upgrades, while remaining well under
	// the ~5x the unbounded append-growth climb used to produce.
	const maxSaneGrowth = 3 * targetSize
	if grown > maxSaneGrowth {
		t.Fatalf("Apply allocated %d bytes reconstructing a %d-byte target from many small copies -- "+
			"want growth bounded near 1x, not the ~5x append-growth-climb regression",
			grown, targetSize)
	}
}

// BenchmarkApply_LargeTarget measures Apply's allocation behavior for a
// target past the 64 KiB initial cap, built from many small copy commands
// (see largeTargetManyCopiesDelta) -- the #81 measurement the issue asks
// for. Run with -benchmem; b.AllocsPerOp/bytes-per-op are the numbers to
// compare across changes to the growth strategy. A single-big-command
// delta (e.g. via Create on disjoint buffers) allocates ~1x on both buggy
// and fixed code and would not show the regression this benchmark exists
// to catch.
func BenchmarkApply_LargeTarget(b *testing.B) {
	source, _, d := largeTargetManyCopiesDelta(b)

	b.ReportAllocs()
	b.ResetTimer()
	for i := 0; i < b.N; i++ {
		if _, err := Apply(source, d); err != nil {
			b.Fatalf("Apply: %v", err)
		}
	}
}

// TestApply_LoopBoundsAgainstTargetDuringCommands is a regression test for
// #82: the command loop used to only compare len(output) against targetLen
// at the ';' terminator, so a delta with enough copy commands could grow
// output well past targetLen before anything noticed. This builds a source
// large enough to serve several sizable copies, declares a small targetLen,
// and supplies far more copy commands than that targetLen could ever
// satisfy -- if the bound were only checked at the terminator (which is
// never reached here), Apply would have to materialize all of them first.
// The test asserts both that Apply rejects the delta and that the actual
// allocation growth stays near the small declared target, not near the
// much larger amount the full command sequence would have produced --
// proof the bound is enforced during the loop, not after it.
func TestApply_LoopBoundsAgainstTargetDuringCommands(t *testing.T) {
	const copySize = 64 * 1024 // 64 KiB per copy command
	const numCopies = 200      // 200 * 64 KiB = 12.5 MiB if left unbounded
	const declaredTarget = 100 * 1024 // 100 KiB: two copies' worth

	source := bytes.Repeat([]byte("x"), copySize)

	var ops []deltaOp
	for i := 0; i < numCopies; i++ {
		ops = append(ops, deltaOp{opType: '@', offset: 0, length: copySize})
	}
	// No terminator: a well-formed delta would fail long before reaching
	// one this large, and this test cares whether the loop stops early,
	// not what error text a terminator mismatch produces.
	delta := manualDelta(declaredTarget, ops, 0)

	runtime.GC()
	var before, after runtime.MemStats
	runtime.ReadMemStats(&before)

	_, err := Apply(source, delta)

	runtime.ReadMemStats(&after)

	if err == nil {
		t.Fatal("expected rejection: copy commands exceed the declared target size")
	}

	grown := after.TotalAlloc - before.TotalAlloc
	// The bound must fire within a small number of commands past
	// declaredTarget, not after all numCopies have been materialized
	// (which would allocate ~numCopies*copySize == 12.5 MiB). A handful
	// of copySize-sized reallocations around the declared target is the
	// expected cost of catching the overrun early; that is a small
	// constant multiple of declaredTarget, not of the full command
	// sequence.
	const growthCeiling = 4 * declaredTarget
	if grown > growthCeiling {
		t.Fatalf("Apply allocated %d bytes before rejecting an over-target delta (declared target %d, %d copy commands of %d bytes each) -- "+
			"want the bound enforced within the loop, not only after materializing everything",
			grown, declaredTarget, numCopies, copySize)
	}
}

func TestApply_ChecksumMismatch(t *testing.T) {
	source := []byte{}
	target := []byte("hello")
	badChecksum := uint32(999999)
	delta := encodeDelta(uint64(len(target)), nil, target, badChecksum)

	_, err := Apply(source, delta)
	if err == nil {
		t.Fatal("expected checksum error")
	}
}

func TestApply_InvalidDelta(t *testing.T) {
	_, err := Apply([]byte{}, []byte{})
	if err == nil {
		t.Fatal("expected error on empty delta")
	}
}

// TestOutputSize verifies that OutputSize reads the target length straight
// out of a delta's header, without touching the source it was created
// against — this is what lets a receiver learn how large a delta will
// expand to before the base is available to apply it.
func TestOutputSize(t *testing.T) {
	source := []byte("original content here")
	target := []byte("original content modified further")
	d := Create(source, target)

	got, err := OutputSize(d)
	if err != nil {
		t.Fatalf("OutputSize: %v", err)
	}
	if got != uint64(len(target)) {
		t.Fatalf("OutputSize = %d, want %d", got, len(target))
	}
}

func TestOutputSize_InvalidDelta(t *testing.T) {
	_, err := OutputSize([]byte("not a delta"))
	if err == nil {
		t.Fatal("expected error for malformed delta header")
	}
}

// TestOutputSize_OverflowRejected is a regression test for wire data that
// overflows the header's integer parse. Eleven base-64 digits at their
// maximum value ('~' == 63) accumulate to exactly math.MaxUint64, which
// casts to int64(-1) -- the same sentinel blob.size uses to mean
// "phantom". A parser that silently wraps instead of rejecting would hand
// StoreDeltaRaw a size that, once cast, makes a freshly-written row with
// real content indistinguishable from a phantom: not re-requestable (no
// phantom-table row), not readable (every "size != -1" check in the
// codebase misclassifies it), permanent corruption from twelve bytes.
//
// This intentionally does not just assert err != nil: a "fix" that
// clamped or saturated the value instead of rejecting it would return a
// non-error result and still be able to produce a negative cast, so the
// value itself is checked whenever no error is returned.
func TestOutputSize_OverflowRejected(t *testing.T) {
	header := []byte("~~~~~~~~~~~\n")

	size, err := OutputSize(header)
	if err == nil {
		if int64(size) < 0 {
			t.Fatalf("OutputSize(overflow header) succeeded with size=%d (int64 %d) -- "+
				"a negative cast is indistinguishable from the phantom sentinel used by blob.size",
				size, int64(size))
		}
		t.Fatalf("OutputSize(overflow header) = %d, want rejection (wire data must not be trusted "+
			"to self-report a size this large)", size)
	}
}

func TestChecksum(t *testing.T) {
	data := []byte("hello")
	c1 := Checksum(data)
	c2 := Checksum(data)
	if c1 != c2 {
		t.Fatalf("Checksum not deterministic: %d != %d", c1, c2)
	}
	c0 := Checksum([]byte{})
	if c0 != 0 {
		t.Fatalf("Checksum(empty) = %d, want 0", c0)
	}
}

func TestCreate_SmallInputs(t *testing.T) {
	tests := []struct {
		name   string
		source string
		target string
	}{
		{"identical", "hello", "hello"},
		{"append", "hello", "hello world"},
		{"prepend", "world", "hello world"},
		{"replace", "aaaa", "bbbb"},
		{"empty_source", "", "new content"},
		{"empty_target", "old content", ""},
	}
	for _, tt := range tests {
		t.Run(tt.name, func(t *testing.T) {
			src := []byte(tt.source)
			tgt := []byte(tt.target)

			d := Create(src, tgt)
			if len(d) == 0 {
				t.Fatal("Create returned empty delta")
			}

			got, err := Apply(src, d)
			if err != nil {
				t.Fatalf("Apply failed: %v", err)
			}
			if !bytes.Equal(got, tgt) {
				t.Fatalf("round-trip failed: got %q, want %q", got, tgt)
			}
		})
	}
}

func TestCreate_LargeInput(t *testing.T) {
	source := bytes.Repeat([]byte("The quick brown fox jumps. "), 4000)
	target := make([]byte, len(source))
	copy(target, source)
	copy(target[50000:], []byte("CHANGED CONTENT HERE!"))

	d := Create(source, target)

	if len(d) > len(target)/2 {
		t.Fatalf("delta too large: %d bytes for %d byte target", len(d), len(target))
	}

	got, err := Apply(source, d)
	if err != nil {
		t.Fatalf("Apply: %v", err)
	}
	if !bytes.Equal(got, target) {
		t.Fatal("round-trip failed for large input")
	}
}

func TestCreate_RoundTrip_FossilValidation(t *testing.T) {
	if testing.Short() {
		t.Skip("skipping fossil validation in short mode")
	}
	source := []byte("original content of the file\nwith multiple lines\nand some data\n")
	target := []byte("original content of the file\nwith MODIFIED lines\nand some data\nplus new stuff\n")

	d := Create(source, target)
	got, err := Apply(source, d)
	if err != nil {
		t.Fatalf("Apply: %v", err)
	}
	if !bytes.Equal(got, target) {
		t.Fatalf("round-trip failed")
	}
}

// TestApplyInto_NilDstMatchesApply pins the delegation: ApplyInto(nil, ...)
// must reconstruct exactly what Apply does, since Apply is defined as that
// call. Goal: prove the fresh-buffer path is untouched by the reuse variant.
func TestApplyInto_NilDstMatchesApply(t *testing.T) {
	source := bytes.Repeat([]byte("abcdefghij"), 200)
	target := append(bytes.Repeat([]byte("abcdefghij"), 199), []byte("CHANGED!")...)
	d := Create(source, target)

	got, err := ApplyInto(nil, source, d)
	if err != nil {
		t.Fatalf("ApplyInto(nil): %v", err)
	}
	if !bytes.Equal(got, target) {
		t.Fatalf("ApplyInto(nil) round-trip failed")
	}

	want, err := Apply(source, d)
	if err != nil {
		t.Fatalf("Apply: %v", err)
	}
	if !bytes.Equal(got, want) {
		t.Fatalf("ApplyInto(nil) differs from Apply")
	}
}

// TestApplyInto_ReusedBufferAllocatesLess is the point of ApplyInto: handed a
// buffer whose capacity already covers the target, it reconstructs in place
// and skips the output allocation Apply always makes. Goal: prove the reuse
// path removes at least the one output allocation, measured via AllocsPerRun
// so it does not depend on the exact allocator count.
func TestApplyInto_ReusedBufferAllocatesLess(t *testing.T) {
	source := bytes.Repeat([]byte("abcdefghij"), 200)
	target := append(bytes.Repeat([]byte("abcdefghij"), 199), []byte("CHANGED!")...)
	d := Create(source, target)

	dst := make([]byte, 0, len(target))

	freshAllocs := testing.AllocsPerRun(200, func() {
		out, err := Apply(source, d)
		if err != nil {
			t.Fatalf("Apply: %v", err)
		}
		if len(out) != len(target) {
			t.Fatalf("Apply produced %d bytes, want %d", len(out), len(target))
		}
	})

	reuseAllocs := testing.AllocsPerRun(200, func() {
		out, err := ApplyInto(dst[:0], source, d)
		if err != nil {
			t.Fatalf("ApplyInto: %v", err)
		}
		if !bytes.Equal(out, target) {
			t.Fatalf("ApplyInto reuse round-trip failed")
		}
	})

	if reuseAllocs >= freshAllocs {
		t.Fatalf("ApplyInto into a pre-sized buffer allocated %.0f times, "+
			"want fewer than Apply's %.0f -- the output allocation was not saved",
			reuseAllocs, freshAllocs)
	}
}

// TestApplyInto_PanicsOnNonEmptyDst guards the reuse contract: the caller must
// hand over a reset buffer (dst[:0]); a non-empty dst would append after live
// bytes and silently corrupt the result. That is a programmer error, so it
// panics rather than returning an error.
func TestApplyInto_PanicsOnNonEmptyDst(t *testing.T) {
	defer func() {
		if recover() == nil {
			t.Fatal("expected panic when dst has non-zero length")
		}
	}()
	source := []byte("source")
	target := []byte("target")
	d := Create(source, target)
	_, _ = ApplyInto([]byte("live"), source, d)
}

func BenchmarkApply(b *testing.B) {
	source := bytes.Repeat([]byte("abcdefghij"), 1000)
	target := append(bytes.Repeat([]byte("abcdefghij"), 999), []byte("CHANGED!")...)
	cs := Checksum(target)
	delta := encodeDelta(uint64(len(target)), nil, target, cs)
	b.ResetTimer()
	for i := 0; i < b.N; i++ {
		Apply(source, delta)
	}
}

func BenchmarkCreate(b *testing.B) {
	source := bytes.Repeat([]byte("abcdefghij"), 1000)
	target := make([]byte, len(source))
	copy(target, source)
	copy(target[5000:], []byte("XXXXXXXXXXXX"))
	b.ResetTimer()
	for i := 0; i < b.N; i++ {
		Create(source, target)
	}
}

// --- Test helpers ---

type deltaOp struct {
	opType byte
	offset uint64
	length uint64
	data   []byte
}

func manualDelta(targetLen uint64, ops []deltaOp, checksum uint32) []byte {
	var buf bytes.Buffer
	writeInt(&buf, targetLen)
	buf.WriteByte('\n')
	for _, op := range ops {
		switch op.opType {
		case '@':
			// Fossil format: count@offset,
			writeInt(&buf, op.length)
			buf.WriteByte('@')
			writeInt(&buf, op.offset)
			buf.WriteByte(',')
		case ':':
			writeInt(&buf, uint64(len(op.data)))
			buf.WriteByte(':')
			buf.Write(op.data)
		}
	}
	writeInt(&buf, uint64(checksum))
	buf.WriteByte(';')
	return buf.Bytes()
}

func encodeDelta(targetLen uint64, source, literal []byte, checksum uint32) []byte {
	var buf bytes.Buffer
	writeInt(&buf, targetLen)
	buf.WriteByte('\n')
	if len(literal) > 0 {
		writeInt(&buf, uint64(len(literal)))
		buf.WriteByte(':')
		buf.Write(literal)
	}
	writeInt(&buf, uint64(checksum))
	buf.WriteByte(';')
	return buf.Bytes()
}

const zDigits = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ_abcdefghijklmnopqrstuvwxyz~"

func writeInt(buf *bytes.Buffer, v uint64) {
	if v == 0 {
		buf.WriteByte('0')
		return
	}
	var tmp [13]byte
	i := len(tmp)
	for v > 0 {
		i--
		tmp[i] = zDigits[v&0x3f]
		v >>= 6
	}
	buf.Write(tmp[i:])
}

// TestApply_ExactSizingAllocatesExactlyOnce pins the property that lets a
// delta-chain replay stop being the allocation hot spot of a clone: when the
// command stream can be walked to its terminator, the output buffer is
// allocated once, at exactly the size the commands were proven to emit.
//
// Two things are asserted, and the capacity one matters as much as the size.
// A buffer that arrives with slack is copied again by content.Cache.store
// (see content.clip) before it can be cached, so every byte of slack is paid
// for twice downstream. Reconstructing the Fossil SCM repository's 8 GiB of
// content used to allocate 200 GiB in this function and hand 60 GiB of
// slack-carrying buffers to that copy; sized exactly, the buffer is allocated
// once and arrives already clipped.
//
// The fixture is the many-small-copies shape (see largeTargetManyCopiesDelta),
// the one that compounds append's ~1.25x large-slice growth. Counting bytes
// rather than nanoseconds keeps this stable on any machine.
func TestApply_ExactSizingAllocatesExactlyOnce(t *testing.T) {
	const targetSize = 1 << 20 // 1 MiB
	source, target, d := largeTargetManyCopiesDelta(t)

	runtime.GC()
	var before, after runtime.MemStats
	runtime.ReadMemStats(&before)

	got, err := Apply(source, d)

	runtime.ReadMemStats(&after)

	if err != nil {
		t.Fatalf("Apply: %v", err)
	}
	if !bytes.Equal(got, target) {
		t.Fatal("round-trip failed")
	}
	if cap(got) != len(got) {
		t.Fatalf("Apply returned len=%d cap=%d -- want a tightly sized buffer, "+
			"slack capacity is copied away again by content.Cache.store",
			len(got), cap(got))
	}

	grown := after.TotalAlloc - before.TotalAlloc
	// One target-sized allocation plus small change. Deliberately tighter than
	// TestApply_LargeTargetAllocationBounded's 3x, which bounds the fallback
	// growth path this test exists to prove is no longer taken.
	const maxSaneGrowth = 3 * targetSize / 2
	if grown > maxSaneGrowth {
		t.Fatalf("Apply allocated %d bytes for a %d-byte target -- want one exact "+
			"allocation, not a climb through the growth path",
			grown, targetSize)
	}
}

// TestApplyInto_ExactSizingReusesAdequateBuffer pins that exact sizing does
// not defeat buffer reuse: a caller ping-ponging two buffers across a chain
// (see content.expandChain) must keep reusing them rather than being handed a
// fresh exact-sized allocation on every link.
func TestApplyInto_ExactSizingReusesAdequateBuffer(t *testing.T) {
	source, target, d := largeTargetManyCopiesDelta(t)

	scratch := make([]byte, 0, 2*len(target))
	got, err := ApplyInto(scratch[:0], source, d)
	if err != nil {
		t.Fatalf("ApplyInto: %v", err)
	}
	if !bytes.Equal(got, target) {
		t.Fatal("round-trip failed")
	}
	if cap(got) != cap(scratch) {
		t.Fatalf("ApplyInto returned a buffer of cap %d, want the supplied %d -- "+
			"an adequate caller buffer must still be reused",
			cap(got), cap(scratch))
	}
}