aboutsummaryrefslogtreecommitdiff
path: root/internal
diff options
context:
space:
mode:
Diffstat (limited to 'internal')
-rw-r--r--internal/compress/zlib/reader.go20
-rw-r--r--internal/compress/zlib/reader_reset.go8
-rw-r--r--internal/format/packidx/bloom/bloom.go180
-rw-r--r--internal/format/packidx/bloom/bloom_test.go159
-rw-r--r--internal/format/packidx/bloom/doc.go138
-rw-r--r--internal/format/packidx/bloom/lookup.go42
-rw-r--r--internal/format/packidx/bloom/lookup_test.go32
-rw-r--r--internal/format/packidx/bloom/roundtrip_test.go92
-rw-r--r--internal/format/packidx/bloom/write.go164
-rw-r--r--internal/format/packidx/bloom/write_test.go95
-rw-r--r--internal/format/packidx/lookup.go48
-rw-r--r--internal/format/packidx/write.go2
-rw-r--r--internal/mru/order.go28
-rw-r--r--internal/mru/order_test.go62
-rw-r--r--internal/mru/touch.go9
-rw-r--r--internal/testgit/command.go2
-rw-r--r--internal/testgit/tree.go2
17 files changed, 1069 insertions, 14 deletions
diff --git a/internal/compress/zlib/reader.go b/internal/compress/zlib/reader.go
index 2de37af4..74357525 100644
--- a/internal/compress/zlib/reader.go
+++ b/internal/compress/zlib/reader.go
@@ -34,6 +34,7 @@ and to read that data back:
package zlib
import (
+ "bytes"
"encoding/binary"
"errors"
"hash"
@@ -75,6 +76,7 @@ type Reader struct {
trailerRead uint64
err error
scratch [4]byte
+ br bytes.Reader
}
// NewReader creates a new ReadCloser.
@@ -100,6 +102,23 @@ func NewReaderDict(r io.Reader, dict []byte) (*Reader, error) {
return z, nil
}
+// NewReaderBytes is like [NewReader] but reads directly from payload,
+// reusing a [bytes.Reader] pooled with the returned Reader
+// instead of allocating a fresh one per call.
+// It is the caller's responsibility to call Close on the ReadCloser when done.
+func NewReaderBytes(payload []byte) (*Reader, error) {
+ z := readerPool.Get()
+
+ z.br.Reset(payload)
+
+ err := z.reset(&z.br, nil)
+ if err != nil {
+ return nil, err
+ }
+
+ return z, nil
+}
+
// Read decompresses bytes from receiver into p.
func (z *Reader) Read(p []byte) (int, error) {
if z.err != nil {
@@ -168,6 +187,7 @@ func (z *Reader) Close() error {
return z.err
}
+ z.br.Reset(nil)
readerPool.Put(z)
return nil
diff --git a/internal/compress/zlib/reader_reset.go b/internal/compress/zlib/reader_reset.go
index 17a8fc4e..6a9340c2 100644
--- a/internal/compress/zlib/reader_reset.go
+++ b/internal/compress/zlib/reader_reset.go
@@ -18,7 +18,7 @@ import (
// reset resets receiver to read a new zlib stream.
func (z *Reader) reset(r io.Reader, dict []byte) error {
- *z = Reader{decompressor: z.decompressor}
+ *z = Reader{decompressor: z.decompressor, digest: z.digest, br: z.br}
var input flate.Reader
if fr, ok := r.(flate.Reader); ok {
@@ -96,7 +96,11 @@ func (z *Reader) reset(r io.Reader, dict []byte) error {
return z.err
}
- z.digest = adler32.New()
+ if z.digest == nil {
+ z.digest = adler32.New()
+ } else {
+ z.digest.Reset()
+ }
return nil
}
diff --git a/internal/format/packidx/bloom/bloom.go b/internal/format/packidx/bloom/bloom.go
new file mode 100644
index 00000000..8b608221
--- /dev/null
+++ b/internal/format/packidx/bloom/bloom.go
@@ -0,0 +1,180 @@
+package bloom
+
+import (
+ "bytes"
+ "encoding/binary"
+ "errors"
+ "fmt"
+ "math/bits"
+
+ "lindenii.org/go/furgit/object/id"
+)
+
+// ErrMalformedBloomFilter reports that
+// a Bloom filter is truncated,
+// has a bad signature, version, or hash function,
+// or has inconsistent parameters.
+var ErrMalformedBloomFilter = errors.New("internal/format/packidx/bloom: malformed bloom filter")
+
+const (
+ signature = 0x4944424c // "IDBL"
+ version = 1
+
+ // HeaderLen is the fixed header length in octets,
+ // i.e., the signature, version, hash function identifier,
+ // B, K, and the trailing zero padding.
+ HeaderLen = 64
+
+ // BucketLen is the length of one bucket in octets,
+ // chosen to match the most common cache-line size.
+ BucketLen = 64
+
+ // wordBits is the bit width of one bucket word.
+ wordBits = 64
+
+ // fieldBits is the width of one in-bucket position field.
+ fieldBits = 9
+)
+
+// checkParams validates the filter parameters
+// against one object hash size,
+// returning log2(bucketCount) on success.
+func checkParams(bucketCount uint32, k uint16, hashSize int) (uint, error) {
+ switch {
+ case bucketCount == 0 || bucketCount&(bucketCount-1) != 0:
+ return 0, errors.New("bucket count not a nonzero power of two") //nolint:err113
+ case k == 0:
+ return 0, errors.New("zero probe count") //nolint:err113
+ }
+
+ log2B := uint(bits.TrailingZeros32(bucketCount))
+ if log2B+fieldBits*uint(k) > uint(hashSize)*8 {
+ return 0, errors.New("parameters exceed hash length") //nolint:err113
+ }
+
+ return log2B, nil
+}
+
+// hashFunctionID returns the on-disk hash function identifier
+// for one object format.
+func hashFunctionID(objectFormat id.ObjectFormat) (uint32, error) {
+ switch objectFormat {
+ case id.ObjectFormatSHA1:
+ return 1, nil
+ case id.ObjectFormatSHA256:
+ return 2, nil
+ case id.ObjectFormatUnknown:
+ }
+
+ return 0, id.ErrInvalidObjectFormat
+}
+
+// Bloom is a parsed blocked Bloom filter view over borrowed bytes.
+//
+// Labels: Deps-Borrowed, Life-Parent, MT-Safe.
+type Bloom struct {
+ // data is the entire filter payload.
+ data []byte
+
+ // buckets is the bucket region, between the header and the trailer.
+ buckets []byte
+
+ // objectFormat is the filter's object format.
+ objectFormat id.ObjectFormat
+
+ // log2B is the base-2 logarithm of the bucket count,
+ // i.e. the number of leading object ID bits that select a bucket.
+ log2B uint
+
+ // k is the number of bits set and tested per object ID.
+ k int
+}
+
+// Parse parses one Bloom filter from data.
+//
+// Labels: Deps-Borrowed, Life-Parent.
+func Parse(data []byte, objectFormat id.ObjectFormat) (Bloom, error) {
+ var zero Bloom
+
+ wantHashID, err := hashFunctionID(objectFormat)
+ if err != nil {
+ return zero, err
+ }
+
+ hashSize := objectFormat.Size()
+
+ if len(data) < HeaderLen {
+ return zero, fmt.Errorf("%w: truncated", ErrMalformedBloomFilter)
+ }
+
+ if binary.BigEndian.Uint32(data) != signature {
+ return zero, fmt.Errorf("%w: bad signature", ErrMalformedBloomFilter)
+ }
+
+ if binary.BigEndian.Uint32(data[4:]) != version {
+ return zero, fmt.Errorf("%w: unsupported version", ErrMalformedBloomFilter)
+ }
+
+ if binary.BigEndian.Uint32(data[8:]) != wantHashID {
+ return zero, fmt.Errorf("%w: hash function mismatch", ErrMalformedBloomFilter)
+ }
+
+ bucketCount := binary.BigEndian.Uint32(data[12:])
+ k := binary.BigEndian.Uint16(data[16:])
+
+ for _, octet := range data[18:HeaderLen] {
+ if octet != 0 {
+ return zero, fmt.Errorf("%w: nonzero padding", ErrMalformedBloomFilter)
+ }
+ }
+
+ log2B, err := checkParams(bucketCount, k, hashSize)
+ if err != nil {
+ return zero, fmt.Errorf("%w: %w", ErrMalformedBloomFilter, err)
+ }
+
+ want := uint64(HeaderLen) + uint64(BucketLen)*uint64(bucketCount) + 2*uint64(hashSize) //#nosec G115
+ if uint64(len(data)) != want {
+ return zero, fmt.Errorf("%w: file size disagrees with bucket count", ErrMalformedBloomFilter)
+ }
+
+ return Bloom{
+ data: data,
+ buckets: data[HeaderLen : len(data)-2*hashSize],
+ objectFormat: objectFormat,
+ log2B: log2B,
+ k: int(k),
+ }, nil
+}
+
+// PackHash returns the pack hash recorded in the filter trailer.
+//
+// Labels: Life-Parent, Mut-No.
+func (f *Bloom) PackHash() []byte {
+ hashSize := f.objectFormat.Size()
+ end := len(f.data) - hashSize
+
+ return f.data[end-hashSize : end]
+}
+
+// Verify recomputes the filter's trailing checksum and reports any mismatch.
+//
+// Verify reads the whole filter,
+// so callers should treat it as a deliberate integrity check
+// rather than part of the open path.
+func (f *Bloom) Verify() error {
+ hashImpl, err := f.objectFormat.New()
+ if err != nil {
+ return fmt.Errorf("internal/format/packidx/bloom: %w", err)
+ }
+
+ checksumOff := len(f.data) - f.objectFormat.Size()
+
+ _, _ = hashImpl.Write(f.data[:checksumOff])
+
+ if !bytes.Equal(hashImpl.Sum(nil), f.data[checksumOff:]) {
+ return fmt.Errorf("%w: checksum mismatch", ErrMalformedBloomFilter)
+ }
+
+ return nil
+}
diff --git a/internal/format/packidx/bloom/bloom_test.go b/internal/format/packidx/bloom/bloom_test.go
new file mode 100644
index 00000000..bcfb4419
--- /dev/null
+++ b/internal/format/packidx/bloom/bloom_test.go
@@ -0,0 +1,159 @@
+package bloom_test
+
+import (
+ "encoding/binary"
+ "errors"
+ "testing"
+
+ "lindenii.org/go/furgit/internal/format/packidx/bloom"
+ "lindenii.org/go/furgit/object/id"
+)
+
+func validFilter(t *testing.T, format id.ObjectFormat) []byte {
+ // TODO: maybe testgit should have something like this?
+ t.Helper()
+
+ builder, err := bloom.NewBuilder(format, 4, 2, make([]byte, format.Size()))
+ if err != nil {
+ t.Fatal(err)
+ }
+
+ return builder.Bytes()
+}
+
+func otherFormat(t *testing.T, format id.ObjectFormat) id.ObjectFormat {
+ t.Helper()
+
+ for _, candidate := range id.SupportedObjectFormats() {
+ if candidate != format {
+ return candidate
+ }
+ }
+
+ t.Skip("only one supported object format")
+
+ return id.ObjectFormatUnknown
+}
+
+func TestParseValid(t *testing.T) {
+ t.Parallel()
+
+ for _, format := range id.SupportedObjectFormats() {
+ t.Run(format.String(), func(t *testing.T) {
+ t.Parallel()
+
+ _, err := bloom.Parse(validFilter(t, format), format)
+ if err != nil {
+ t.Fatalf("Parse rejected a valid filter: %v", err)
+ }
+ })
+ }
+}
+
+func TestParseMalformed(t *testing.T) {
+ t.Parallel()
+
+ cases := []struct {
+ name string
+ mangle func(data []byte) []byte
+ }{
+ {"truncated", func(data []byte) []byte { return data[:bloom.HeaderLen-1] }},
+ {"bad signature", func(data []byte) []byte {
+ data[0] ^= 0xff
+
+ return data
+ }},
+ {"bad version", func(data []byte) []byte {
+ binary.BigEndian.PutUint32(data[4:], 99)
+
+ return data
+ }},
+ {"non power of two", func(data []byte) []byte {
+ binary.BigEndian.PutUint32(data[12:], 3)
+
+ return data
+ }},
+ {"zero probe count", func(data []byte) []byte {
+ binary.BigEndian.PutUint16(data[16:], 0)
+
+ return data
+ }},
+ {"parameters exceed hash", func(data []byte) []byte {
+ binary.BigEndian.PutUint32(data[12:], 1<<31)
+ binary.BigEndian.PutUint16(data[16:], 30)
+
+ return data
+ }},
+ {"nonzero padding", func(data []byte) []byte {
+ data[20] = 1
+
+ return data
+ }},
+ {"size disagrees", func(data []byte) []byte { return data[:len(data)-1] }},
+ }
+
+ for _, format := range id.SupportedObjectFormats() {
+ t.Run(format.String(), func(t *testing.T) {
+ t.Parallel()
+
+ for _, tc := range cases {
+ t.Run(tc.name, func(t *testing.T) {
+ t.Parallel()
+
+ data := tc.mangle(append([]byte(nil), validFilter(t, format)...))
+
+ _, err := bloom.Parse(data, format)
+ if !errors.Is(err, bloom.ErrMalformedBloomFilter) {
+ t.Fatalf("Parse error = %v, want ErrMalformedBloomFilter", err)
+ }
+ })
+ }
+ })
+ }
+}
+
+// TestVerifyDetectsCorruption checks that Verify accepts a sound filter
+// and rejects one whose bucket bytes have been altered.
+func TestVerifyDetectsCorruption(t *testing.T) {
+ t.Parallel()
+
+ for _, format := range id.SupportedObjectFormats() {
+ t.Run(format.String(), func(t *testing.T) {
+ t.Parallel()
+
+ data := validFilter(t, format)
+
+ filter, err := bloom.Parse(data, format)
+ if err != nil {
+ t.Fatal(err)
+ }
+
+ err = filter.Verify()
+ if err != nil {
+ t.Fatalf("Verify on a sound filter: %v", err)
+ }
+
+ data[bloom.HeaderLen] ^= 0xff
+
+ err = filter.Verify()
+ if !errors.Is(err, bloom.ErrMalformedBloomFilter) {
+ t.Fatalf("Verify error = %v, want ErrMalformedBloomFilter", err)
+ }
+ })
+ }
+}
+
+func TestParseHashMismatch(t *testing.T) {
+ t.Parallel()
+
+ for _, format := range id.SupportedObjectFormats() {
+ t.Run(format.String(), func(t *testing.T) {
+ t.Parallel()
+
+ _, err := bloom.Parse(validFilter(t, format), otherFormat(t, format))
+ if !errors.Is(err, bloom.ErrMalformedBloomFilter) {
+ t.Fatalf("Parse error = %v, want ErrMalformedBloomFilter", err)
+ }
+ })
+ }
+}
diff --git a/internal/format/packidx/bloom/doc.go b/internal/format/packidx/bloom/doc.go
new file mode 100644
index 00000000..06ca57cd
--- /dev/null
+++ b/internal/format/packidx/bloom/doc.go
@@ -0,0 +1,138 @@
+// Package bloom provides a blocked Bloom filter
+// for pack indexes.
+//
+// A filter answers, from a single cache-line-sized read,
+// whether an object ID is definitely absent from the index it covers.
+// A lookup that must consult many packs
+// can then skip the full binary search
+// in every pack whose filter rejects the object,
+// decreasing the cost of misses.
+//
+// # Rationale
+//
+// Especially for server-side usage,
+// repacking is expensive,
+// and creating multi-pack-indexes is still rather expensive.
+// Incremental multi-pack-indexes partially solve this,
+// but having too many of them defeats the purpose,
+// since the indexes must still be walked in order
+// while performing expensive lookups.
+//
+// Instead, each multi-pack-index layer,
+// and each ordinary pack index,
+// may carry its own filter.
+// The indexes are still traversed in their usual order,
+// but the first step when traversing one
+// is to check whether it could possibly hold the wanted object.
+//
+// The filter is split into 64-octet buckets,
+// matching the most common cache-line size.
+// Some bits of the object ID choose the bucket,
+// and the rest choose several bit positions inside it,
+// so a lookup reads one 64-octet bucket
+// and checks whether all required bits are set.
+//
+// # Parameters
+//
+// A filter is parameterized by
+// the number of buckets B
+// and the number of bits set and tested per object ID, K.
+// All integers in the format are big endian.
+// The object ID is interpreted as a big-endian bitstring,
+// where bit offset 0 is the most significant bit of octet 0.
+// B must be a nonzero power of two,
+// K must be nonzero,
+// and log2(B) + 9*K must not exceed the hash length in bits.
+//
+// # File format
+//
+// A filter file is a 64-octet header,
+// then B buckets of 64 octets each,
+// then a two-hash trailer:
+//
+// - 4-octet signature: {'I', 'D', 'B', 'L'}.
+// - 4-octet version identifier (= 1).
+// - 4-octet object hash algorithm identifier
+// (= 1 for SHA-1, 2 for SHA-256).
+// - 4-octet B, the number of buckets.
+// - 2-octet K, the number of bits set and tested per object ID.
+// - 46-octet padding, which must be all zero.
+// - B buckets of 64 octets each.
+// - the pack trailer hash, which binds the filter to its pack.
+// - the checksum of everything before it, over the filter's hash function.
+//
+// The hash length is that of the object format,
+// so the trailer is 2 hashes wide
+// and the file size is exactly 64 + 64*B + 2*hashlen octets.
+//
+// A reader must validate that
+// the signature matches,
+// the version is supported,
+// the hash function identifier is recognized,
+// B is nonzero and a power of two,
+// K is nonzero,
+// log2(B) + 9*K does not exceed the hash length in bits,
+// the padding is all zero,
+// and the file size is exactly 64 + 64*B + 2*hashlen octets.
+//
+// # Binding and integrity
+//
+// The pack hash binds a filter to one pack;
+// a reader trusts a filter only when the recorded pack hash
+// matches the pack it accompanies.
+//
+// The checksum guards against corruption of the filter itself.
+// Recomputing it reads the whole file and rehashes it as fsck.
+//
+// # Lookup
+//
+// A lookup against one filter proceeds as follows:
+//
+// 1. Let b be the unsigned integer encoded
+// by the most significant log2(B) bits of the object ID.
+// B is a power of two, so 0 <= b < B.
+// 2. Select and read bucket b.
+// 3. For each 0 <= i < K,
+// take the i-th 9-bit field
+// from the 9*K bits that follow the bucket-selecting bits,
+// and let pi be the unsigned integer it encodes,
+// so 0 <= pi < 512.
+// Compute wi = pi >> 6 and bi = pi & 63,
+// so wi identifies one of the eight 64-bit words in bucket b
+// and bi identifies one bit within that word.
+// Within each 64-bit word,
+// bit index 0 is the most significant bit
+// and bit index 63 is the least significant bit.
+// Test whether bit bi is set in word wi of bucket b.
+//
+// If any test fails,
+// the object ID is definitely not in the covered index.
+// If all tests succeed,
+// the object ID may be in it.
+// Two of the K 9-bit fields can decode to the same pi,
+// so an insertion may set fewer than K distinct bits;
+// this only raises the false positive rate
+// and never causes a false negative.
+//
+// # Worked example
+//
+// Let B = 1 << 15 = 32768 and K = 8.
+// Then log2(B) = 15,
+// so each lookup uses 15 bits to choose the bucket
+// and 8*9 = 72 bits to choose the in-bucket positions,
+// for a total of 87 bits taken from the object ID.
+// A SHA-1 has 160 bits and a SHA-256 has 256 bits,
+// so both leave ample headroom.
+//
+// # Security considerations
+//
+// Object IDs are public unkeyed hashes,
+// so an adversary can mine packs
+// whose object IDs share a chosen prefix
+// to crowd objects into one bucket
+// and fill its bits.
+// In the worst case this renders some buckets useless,
+// making the filter degrade to "may contain" for those buckets,
+// but it never produces a false negative
+// and is not a significant denial-of-service vector.
+package bloom
diff --git a/internal/format/packidx/bloom/lookup.go b/internal/format/packidx/bloom/lookup.go
new file mode 100644
index 00000000..4a8d7bda
--- /dev/null
+++ b/internal/format/packidx/bloom/lookup.go
@@ -0,0 +1,42 @@
+package bloom
+
+import (
+ "encoding/binary"
+)
+
+// MayContain reports whether oid may be present
+// in the index covered by the filter.
+//
+// oid must be exactly the filter's hash size;
+// MayContain panics otherwise.
+//
+// Labels: Mut-No.
+func (f *Bloom) MayContain(oid []byte) bool {
+ if len(oid) != f.objectFormat.Size() {
+ panic("internal/format/packidx/bloom: invalid object ID length")
+ }
+
+ base := int(binary.BigEndian.Uint32(oid[:4])>>(32-f.log2B)) * BucketLen
+
+ for i := range f.k {
+ word, mask := probe(oid, f.log2B, i)
+ if binary.BigEndian.Uint64(f.buckets[base+word*8:])&mask == 0 {
+ return false
+ }
+ }
+
+ return true
+}
+
+// probe returns the bucket word index and single-bit mask
+// addressed by the i-th probe of oid.
+func probe(oid []byte, log2B uint, i int) (word int, mask uint64) {
+ bitOff := log2B + fieldBits*uint(i)
+ byteOff := bitOff >> 3
+ bitInByte := bitOff & 7
+
+ window := uint32(oid[byteOff])<<8 | uint32(oid[byteOff+1])
+ pi := (window >> (16 - bitInByte - fieldBits)) & 0x1ff
+
+ return int(pi >> 6), 1 << (wordBits - 1 - (pi & 63))
+}
diff --git a/internal/format/packidx/bloom/lookup_test.go b/internal/format/packidx/bloom/lookup_test.go
new file mode 100644
index 00000000..e6264f9a
--- /dev/null
+++ b/internal/format/packidx/bloom/lookup_test.go
@@ -0,0 +1,32 @@
+package bloom_test
+
+import (
+ "testing"
+
+ "lindenii.org/go/furgit/internal/format/packidx/bloom"
+ "lindenii.org/go/furgit/object/id"
+)
+
+func TestMayContainBadLength(t *testing.T) {
+ t.Parallel()
+
+ format := id.ObjectFormatSHA256
+
+ builder, err := bloom.NewBuilder(format, 4, 2, make([]byte, format.Size()))
+ if err != nil {
+ t.Fatal(err)
+ }
+
+ filter, err := bloom.Parse(builder.Bytes(), format)
+ if err != nil {
+ t.Fatal(err)
+ }
+
+ defer func() {
+ if recover() == nil {
+ t.Fatal("MayContain did not panic on a short object ID")
+ }
+ }()
+
+ filter.MayContain(make([]byte, format.Size()-1))
+}
diff --git a/internal/format/packidx/bloom/roundtrip_test.go b/internal/format/packidx/bloom/roundtrip_test.go
new file mode 100644
index 00000000..28db17a5
--- /dev/null
+++ b/internal/format/packidx/bloom/roundtrip_test.go
@@ -0,0 +1,92 @@
+package bloom_test
+
+import (
+ "bytes"
+ "encoding/binary"
+ "testing"
+
+ "lindenii.org/go/furgit/internal/format/packidx/bloom"
+ "lindenii.org/go/furgit/object/id"
+)
+
+func makeOID(size int, seed uint64) []byte {
+ out := make([]byte, size)
+ state := seed
+
+ for i := 0; i < size; i += 8 {
+ state = state*6364136223846793005 + 1442695040888963407
+
+ var word [8]byte
+
+ binary.BigEndian.PutUint64(word[:], state)
+ copy(out[i:], word[:])
+ }
+
+ return out
+}
+
+func TestRoundTrip(t *testing.T) {
+ t.Parallel()
+
+ for _, format := range id.SupportedObjectFormats() {
+ t.Run(format.String(), func(t *testing.T) {
+ t.Parallel()
+
+ const objects = 10000
+
+ bucketCount, k, err := bloom.RecommendParams(format, objects)
+ if err != nil {
+ t.Fatal(err)
+ }
+
+ size := format.Size()
+ packHash := makeOID(size, 0xC0FFEE)
+
+ builder, err := bloom.NewBuilder(format, bucketCount, k, packHash)
+ if err != nil {
+ t.Fatal(err)
+ }
+
+ for i := range objects {
+ builder.Add(makeOID(size, uint64(i)))
+ }
+
+ filter, err := bloom.Parse(builder.Bytes(), format)
+ if err != nil {
+ t.Fatal(err)
+ }
+
+ if !bytes.Equal(filter.PackHash(), packHash) {
+ t.Fatalf("PackHash = %x, want %x", filter.PackHash(), packHash)
+ }
+
+ err = filter.Verify()
+ if err != nil {
+ t.Fatalf("Verify on a freshly built filter: %v", err)
+ }
+
+ for i := range objects {
+ if !filter.MayContain(makeOID(size, uint64(i))) {
+ t.Fatalf("false negative for added object %d", i)
+ }
+ }
+
+ const probes = 10000
+
+ falsePositives := 0
+
+ for i := range probes {
+ if filter.MayContain(makeOID(size, uint64(1)<<40+uint64(i))) {
+ falsePositives++
+ }
+ }
+
+ rate := float64(falsePositives) / float64(probes)
+ if rate > 0.05 {
+ t.Errorf("false positive rate %.4f exceeds 0.05", rate)
+ }
+
+ t.Logf("B=%d K=%d false positive rate %.4f", bucketCount, k, rate)
+ })
+ }
+}
diff --git a/internal/format/packidx/bloom/write.go b/internal/format/packidx/bloom/write.go
new file mode 100644
index 00000000..e6213a2c
--- /dev/null
+++ b/internal/format/packidx/bloom/write.go
@@ -0,0 +1,164 @@
+package bloom
+
+import (
+ "encoding/binary"
+ "errors"
+ "fmt"
+ "hash"
+ "math/bits"
+
+ "lindenii.org/go/furgit/object/id"
+ "lindenii.org/go/lgo/intconv"
+)
+
+// ErrInvalidParameters reports that
+// the parameters supplied for a filter build
+// are not representable in the format.
+var ErrInvalidParameters = errors.New("internal/format/packidx/bloom: invalid parameters")
+
+// defaultK is the probe count used by [RecommendParams].
+//
+// With 512-bit buckets it keeps the false positive rate near one percent
+// at the target bucket load.
+const defaultK = 8
+
+// targetLoad is the object count per bucket that [RecommendParams] aims for.
+const targetLoad = 48
+
+// Builder accumulates object IDs into an in-memory Bloom filter
+// and serializes it.
+//
+// Labels: MT-Unsafe.
+type Builder struct {
+ // data is the full filter file, header and trailer included.
+ data []byte
+
+ // buckets aliases the bucket region of data, between header and trailer.
+ buckets []byte
+
+ // hashImpl computes the trailing checksum and gives the hash size.
+ hashImpl hash.Hash
+
+ log2B uint
+ k int
+}
+
+// NewBuilder creates a filter builder
+// for bucketCount buckets and k probes per object ID,
+// binding the filter to packHash.
+//
+// bucketCount must be a nonzero power of two,
+// k must be nonzero,
+// and log2(bucketCount) + 9*k must not exceed the hash length in bits.
+// packHash must be the pack's trailer hash;
+// NewBuilder panics when its length does not match the object format.
+func NewBuilder(objectFormat id.ObjectFormat, bucketCount uint32, k uint16, packHash []byte) (*Builder, error) {
+ hashID, err := hashFunctionID(objectFormat)
+ if err != nil {
+ return nil, err
+ }
+
+ hashImpl, err := objectFormat.New()
+ if err != nil {
+ return nil, fmt.Errorf("internal/format/packidx/bloom: %w", err)
+ }
+
+ hashSize := objectFormat.Size()
+
+ if len(packHash) != hashSize {
+ panic("internal/format/packidx/bloom: invalid pack hash length")
+ }
+
+ log2B, err := checkParams(bucketCount, k, hashSize)
+ if err != nil {
+ return nil, fmt.Errorf("%w: %w", ErrInvalidParameters, err)
+ }
+
+ total, err := intconv.Uint64ToInt(uint64(HeaderLen) + uint64(BucketLen)*uint64(bucketCount) + 2*uint64(hashSize)) //#nosec G115
+ if err != nil {
+ return nil, fmt.Errorf("%w: %w", ErrInvalidParameters, err)
+ }
+
+ data := make([]byte, total)
+ binary.BigEndian.PutUint32(data[0:], signature)
+ binary.BigEndian.PutUint32(data[4:], version)
+ binary.BigEndian.PutUint32(data[8:], hashID)
+ binary.BigEndian.PutUint32(data[12:], bucketCount)
+ binary.BigEndian.PutUint16(data[16:], k)
+
+ bucketsEnd := total - 2*hashSize
+ copy(data[bucketsEnd:], packHash)
+
+ return &Builder{
+ data: data,
+ buckets: data[HeaderLen:bucketsEnd],
+ hashImpl: hashImpl,
+ log2B: log2B,
+ k: int(k),
+ }, nil
+}
+
+// Add records oid in the filter.
+//
+// oid must be exactly the filter's hash size;
+// Add panics otherwise.
+func (b *Builder) Add(oid []byte) {
+ if len(oid) != b.hashImpl.Size() {
+ panic("internal/format/packidx/bloom: invalid object ID length")
+ }
+
+ base := int(binary.BigEndian.Uint32(oid[:4])>>(32-b.log2B)) * BucketLen
+
+ for i := range b.k {
+ word, mask := probe(oid, b.log2B, i)
+
+ off := base + word*8
+ set := binary.BigEndian.Uint64(b.buckets[off:]) | mask
+ binary.BigEndian.PutUint64(b.buckets[off:], set)
+ }
+}
+
+// Bytes returns the serialized filter, including its trailing checksum.
+//
+// Labels: Life-Parent, Mut-No.
+func (b *Builder) Bytes() []byte {
+ checksumOff := len(b.data) - b.hashImpl.Size()
+
+ b.hashImpl.Reset()
+ _, _ = b.hashImpl.Write(b.data[:checksumOff])
+ b.hashImpl.Sum(b.data[checksumOff:checksumOff])
+
+ return b.data
+}
+
+// RecommendParams returns filter parameters for an index of n objects,
+// targeting a false positive rate near one percent.
+func RecommendParams(objectFormat id.ObjectFormat, n int) (bucketCount uint32, k uint16, err error) {
+ hashSize := objectFormat.Size()
+ if hashSize == 0 {
+ return 0, 0, id.ErrInvalidObjectFormat
+ }
+
+ const maxPow2 = uint32(1) << 31
+
+ wanted := uint64(0)
+ if n > 0 {
+ wanted = (uint64(n) + targetLoad - 1) / targetLoad
+ }
+
+ switch {
+ case wanted <= 1:
+ bucketCount = 1
+ case wanted > uint64(maxPow2):
+ bucketCount = maxPow2
+ default:
+ bucketCount = uint32(1) << bits.Len64(wanted-1)
+ }
+
+ _, err = checkParams(bucketCount, defaultK, hashSize)
+ if err != nil {
+ return 0, 0, fmt.Errorf("%w: %w", ErrInvalidParameters, err)
+ }
+
+ return bucketCount, defaultK, nil
+}
diff --git a/internal/format/packidx/bloom/write_test.go b/internal/format/packidx/bloom/write_test.go
new file mode 100644
index 00000000..74173921
--- /dev/null
+++ b/internal/format/packidx/bloom/write_test.go
@@ -0,0 +1,95 @@
+package bloom_test
+
+import (
+ "errors"
+ "testing"
+
+ "lindenii.org/go/furgit/internal/format/packidx/bloom"
+ "lindenii.org/go/furgit/object/id"
+)
+
+func TestRecommendParams(t *testing.T) {
+ t.Parallel()
+
+ for _, format := range id.SupportedObjectFormats() {
+ t.Run(format.String(), func(t *testing.T) {
+ t.Parallel()
+
+ for _, n := range []int{0, 1, 1000, 10000, 1000000} {
+ bucketCount, k, err := bloom.RecommendParams(format, n)
+ if err != nil {
+ t.Fatalf("n=%d: %v", n, err)
+ }
+
+ if bucketCount == 0 || bucketCount&(bucketCount-1) != 0 {
+ t.Errorf("n=%d: bucket count %d not a power of two", n, bucketCount)
+ }
+
+ _, err = bloom.NewBuilder(format, bucketCount, k, make([]byte, format.Size()))
+ if err != nil {
+ t.Errorf("n=%d: recommended parameters rejected: %v", n, err)
+ }
+ }
+ })
+ }
+}
+
+func TestNewBuilderRejects(t *testing.T) {
+ t.Parallel()
+
+ cases := []struct {
+ name string
+ bucketCount uint32
+ k uint16
+ }{
+ {"zero buckets", 0, 8},
+ {"non power of two", 3, 8},
+ {"zero probe count", 4, 0},
+ }
+
+ for _, format := range id.SupportedObjectFormats() {
+ t.Run(format.String(), func(t *testing.T) {
+ t.Parallel()
+
+ for _, tc := range cases {
+ t.Run(tc.name, func(t *testing.T) {
+ t.Parallel()
+
+ _, err := bloom.NewBuilder(format, tc.bucketCount, tc.k, make([]byte, format.Size()))
+ if !errors.Is(err, bloom.ErrInvalidParameters) {
+ t.Fatalf("error = %v, want ErrInvalidParameters", err)
+ }
+ })
+ }
+ })
+ }
+}
+
+func TestNewBuilderBadPackHash(t *testing.T) {
+ t.Parallel()
+
+ defer func() {
+ if recover() == nil {
+ t.Fatal("NewBuilder did not panic on a short pack hash")
+ }
+ }()
+
+ _, _ = bloom.NewBuilder(id.ObjectFormatSHA256, 4, 2, make([]byte, id.ObjectFormatSHA256.Size()-1))
+}
+
+func TestAddBadLength(t *testing.T) {
+ t.Parallel()
+
+ builder, err := bloom.NewBuilder(id.ObjectFormatSHA256, 4, 2, make([]byte, id.ObjectFormatSHA256.Size()))
+ if err != nil {
+ t.Fatal(err)
+ }
+
+ defer func() {
+ if recover() == nil {
+ t.Fatal("Add did not panic on a short object ID")
+ }
+ }()
+
+ builder.Add(make([]byte, id.ObjectFormatSHA256.Size()-1))
+}
diff --git a/internal/format/packidx/lookup.go b/internal/format/packidx/lookup.go
index d1293f47..e4b565b6 100644
--- a/internal/format/packidx/lookup.go
+++ b/internal/format/packidx/lookup.go
@@ -4,6 +4,7 @@ import (
"bytes"
"encoding/binary"
"fmt"
+ "math/bits"
)
// Lookup searches the index for one object ID
@@ -18,6 +19,53 @@ func (idx *Packidx) Lookup(oid []byte) (offset uint64, found bool, err error) {
lo, hi := idx.fanoutRange(oid[0])
+ // Object IDs are uniform for honest inputs,
+ // interp on next 8 octets converges in O(log log n).
+ //
+ // OIDs are public unkeyed hashes,
+ // so an attacker may sample/filter/mine prefix clusters,
+ // making interpolation mis-estimate every probe.
+ // See https://runxiyu.org/comp/ch4ht/
+ // for why cryptographic hash algorithms are insufficient.
+ //
+ // Cap the interp at bisect's probe count and finish by bisect;
+ // adversarial at O(log n) plus small interpolation overhead,
+ // honest exit well under the cap.
+ target := binary.BigEndian.Uint64(oid[1:9])
+
+ for budget := bits.Len(uint(hi - lo)); hi-lo > 8 && budget > 0; budget-- {
+ loKey := binary.BigEndian.Uint64(idx.OIDAt(lo)[1:9])
+ hiKey := binary.BigEndian.Uint64(idx.OIDAt(hi - 1)[1:9])
+
+ var mid int
+
+ switch {
+ case target <= loKey:
+ mid = lo
+ case target >= hiKey:
+ mid = hi - 1
+ default:
+ hi128, lo128 := bits.Mul64(target-loKey, uint64(hi-lo-1)) //#nosec G115
+ q, _ := bits.Div64(hi128, lo128, hiKey-loKey)
+ mid = lo + int(q) //#nosec G115
+ }
+
+ switch cmp := bytes.Compare(oid, idx.OIDAt(mid)); {
+ case cmp == 0:
+ offset, err = idx.OffsetAt(mid)
+ if err != nil {
+ return 0, false, err
+ }
+
+ return offset, true, nil
+ case cmp < 0:
+ hi = mid
+ default:
+ lo = mid + 1
+ }
+ }
+
+ // Interpolation narrowed or capped; bisect to finish.
for lo < hi {
mid := lo + (hi-lo)/2
diff --git a/internal/format/packidx/write.go b/internal/format/packidx/write.go
index d3f22c83..35b2805f 100644
--- a/internal/format/packidx/write.go
+++ b/internal/format/packidx/write.go
@@ -84,7 +84,7 @@ func Write(w io.Writer, objectFormat id.ObjectFormat, entries []Entry, packHash
sw.PutUint32(entries[i].CRC32)
}
- var largeOffsets []uint64
+ largeOffsets := make([]uint64, 0, len(entries))
for i := range entries {
offset := entries[i].Offset
diff --git a/internal/mru/order.go b/internal/mru/order.go
index 76b58497..1ea1ac09 100644
--- a/internal/mru/order.go
+++ b/internal/mru/order.go
@@ -22,11 +22,33 @@ import (
type Order[K comparable] struct {
snapshot atomic.Pointer[[]K]
mu sync.Mutex
+
+ interval uint64
+ pending atomic.Uint64
+}
+
+// Options configures a new Order.
+type Options struct {
+ // Interval applies a reorder at most once per Interval
+ // eligible (non-front, member) Touch calls.
+ //
+ // A larger Interval decreases recency precision
+ // but uses fewer allocations.
+ // Each applied reorder allocates one snapshot,
+ // so throttling decreases the snapshot-allocation rate
+ // by roughly Interval.
+ //
+ // An Interval of 1 reorders on every eligible Touch.
+ Interval uint64
}
-// New returns a new, empty order.
-func New[K comparable]() *Order[K] {
- return &Order[K]{} //nolint:exhaustruct
+// New returns a new, empty order configured by opts.
+func New[K comparable](opts Options) *Order[K] {
+ if opts.Interval == 0 {
+ panic("internal/mru: Options.Interval must be at least 1")
+ }
+
+ return &Order[K]{interval: opts.Interval} //nolint:exhaustruct
}
// Len returns the number of keys in the order.
diff --git a/internal/mru/order_test.go b/internal/mru/order_test.go
index bf0d4f2e..2f16eac3 100644
--- a/internal/mru/order_test.go
+++ b/internal/mru/order_test.go
@@ -20,7 +20,7 @@ func set(keys ...string) map[string]struct{} {
func TestTouchMovesToFront(t *testing.T) {
t.Parallel()
- order := mru.New[string]()
+ order := mru.New[string](mru.Options{Interval: 1})
order.Sync(set("a", "b", "c"))
order.Touch("a")
@@ -36,10 +36,60 @@ func TestTouchMovesToFront(t *testing.T) {
}
}
+func TestIntervalThrottlesReorder(t *testing.T) {
+ t.Parallel()
+
+ const interval = 4
+
+ order := mru.New[string](mru.Options{Interval: interval})
+ order.Sync(set("a", "b", "c"))
+
+ front := order.Keys()[0]
+
+ other := "a"
+ if other == front {
+ other = "b"
+ }
+
+ for range interval - 1 {
+ order.Touch(other)
+
+ if got := order.Keys()[0]; got != front {
+ t.Fatalf("reordered early: front = %q, want %q", got, front)
+ }
+ }
+
+ order.Touch(other)
+
+ if got := order.Keys()[0]; got != other {
+ t.Fatalf("after interval touches, front = %q, want %q", got, other)
+ }
+}
+
+func TestIntervalKeepsMembershipUnderReorder(t *testing.T) {
+ t.Parallel()
+
+ order := mru.New[string](mru.Options{Interval: 8})
+ order.Sync(set("a", "b", "c", "d"))
+
+ for range 100 {
+ for _, key := range []string{"a", "b", "c", "d"} {
+ order.Touch(key)
+ }
+ }
+
+ got := slices.Clone(order.Keys())
+ slices.Sort(got)
+
+ if want := []string{"a", "b", "c", "d"}; !slices.Equal(got, want) {
+ t.Fatalf("membership corrupted: %v", got)
+ }
+}
+
func TestSyncDropsAbsentAndKeepsSurvivorOrder(t *testing.T) {
t.Parallel()
- order := mru.New[string]()
+ order := mru.New[string](mru.Options{Interval: 1})
order.Sync(set("a", "b", "c"))
// Establish a deterministic recency order: c, b, a.
@@ -61,7 +111,7 @@ func TestSyncDropsAbsentAndKeepsSurvivorOrder(t *testing.T) {
func TestSyncPlacesNewKeysFirst(t *testing.T) {
t.Parallel()
- order := mru.New[string]()
+ order := mru.New[string](mru.Options{Interval: 1})
order.Sync(set("a", "b"))
order.Touch("a")
@@ -77,7 +127,7 @@ func TestSyncPlacesNewKeysFirst(t *testing.T) {
func TestTouchAbsentIsNoOp(t *testing.T) {
t.Parallel()
- order := mru.New[string]()
+ order := mru.New[string](mru.Options{Interval: 1})
order.Sync(set("a", "b"))
order.Touch("a")
order.Touch("z")
@@ -90,7 +140,7 @@ func TestTouchAbsentIsNoOp(t *testing.T) {
func TestKeysIsConsistentSnapshot(t *testing.T) {
t.Parallel()
- order := mru.New[string]()
+ order := mru.New[string](mru.Options{Interval: 1})
order.Sync(set("a", "b"))
snapshot := order.Keys()
@@ -111,7 +161,7 @@ func TestKeysIsConsistentSnapshot(t *testing.T) {
func TestConcurrentTouchAndKeys(t *testing.T) {
t.Parallel()
- order := mru.New[string]()
+ order := mru.New[string](mru.Options{Interval: 1})
order.Sync(set("a", "b", "c", "d"))
var wg sync.WaitGroup
diff --git a/internal/mru/touch.go b/internal/mru/touch.go
index 67ac6706..420bbc4a 100644
--- a/internal/mru/touch.go
+++ b/internal/mru/touch.go
@@ -10,12 +10,21 @@ package mru
// A contended attempt,
// or a key that is not a member,
// leaves the order unchanged.
+//
+// When the order has a reorder interval above 1,
+// an eligible (non-front) Touch records its recency
+// but applies the reorder only once per interval such calls;
+// the recording itself is lock-free and allocation-free.
func (order *Order[K]) Touch(key K) {
keys := order.Keys()
if len(keys) == 0 || keys[0] == key {
return
}
+ if order.interval > 1 && order.pending.Add(1)%order.interval != 0 {
+ return
+ }
+
if !order.mu.TryLock() {
return
}
diff --git a/internal/testgit/command.go b/internal/testgit/command.go
index db874bd1..4e696ece 100644
--- a/internal/testgit/command.go
+++ b/internal/testgit/command.go
@@ -15,7 +15,7 @@ func (repo *Repo) command(
) *exec.Cmd {
tb.Helper()
- cmd := exec.CommandContext(tb.Context(), command, args...) //nolint:gosec // Test helper runs caller-selected commands.
+ cmd := exec.CommandContext(tb.Context(), command, args...) //nolint:gosec
cmd.Dir = repo.path
cmd.Env = repo.env
diff --git a/internal/testgit/tree.go b/internal/testgit/tree.go
index 501c7949..ff9b1918 100644
--- a/internal/testgit/tree.go
+++ b/internal/testgit/tree.go
@@ -50,7 +50,7 @@ func (repo *Repo) LsTree(tb testing.TB, oid id.ObjectID) ([]TreeEntry, error) {
return nil, fmt.Errorf("ls-tree: %w", err)
}
- var entries []TreeEntry
+ entries := make([]TreeEntry, 0, bytes.Count(stdout, []byte{0}))
for record := range bytes.SplitSeq(stdout, []byte{0}) {
if len(record) == 0 {
generated by cgit v1.3.1-10-gc9f91 (git 2.54.0) at 2026-06-24 23:24:00 +0000