object/store/packed: Skip if bloom filter says impossible

2 files changed, 42 insertions, 8 deletions

diff --git a/object/store/packed/lookup.go b/object/store/packed/lookup.go
index e54d34b2..e06870a9 100644
--- a/object/store/packed/lookup.go
+++ b/object/store/packed/lookup.go
@@ -24,6 +24,10 @@ func (packed *Packed) lookup(objectID id.ObjectID) (*pack, int, error) {
 	oid := objectID.RawBytes()
 
 	for _, p := range packed.order.Keys() {
+		if p.filter != nil && !p.filter.MayContain(oid) {
+			continue
+		}
+
 		offsetU, found, err := p.idx.Lookup(oid)
 		if err != nil {
 			return nil, 0, fmt.Errorf("%w: pack %q: %w", ErrMalformedPackedStore, p.name, err)
diff --git a/object/store/packed/pack.go b/object/store/packed/pack.go
index dd43bc7a..ba865e51 100644
--- a/object/store/packed/pack.go
+++ b/object/store/packed/pack.go
@@ -8,6 +8,7 @@ import (
 
 	"lindenii.org/go/furgit/internal/format/packfile"
 	"lindenii.org/go/furgit/internal/format/packidx"
+	"lindenii.org/go/furgit/internal/format/packidx/bloom"
 	"lindenii.org/go/furgit/internal/mmap"
 	"lindenii.org/go/furgit/object/id"
 	"lindenii.org/go/lgo/intconv"
@@ -36,6 +37,9 @@ type pack struct {
 	// and data aliases them.
 	dataMapping *mmap.Mmap
 	data        []byte
+
+	bloomMapping *mmap.Mmap
+	filter       *bloom.Bloom
 }
 
 // openPack opens, maps, and validates
@@ -69,15 +73,35 @@ func openPack(root *os.Root, name string, objectFormat id.ObjectFormat) (*pack,
 		return nil, fmt.Errorf("%w: pack %q: %w", ErrMalformedPackedStore, name, err)
 	}
 
+	bloomMapping, filter := openBloom(root, name, objectFormat)
+
 	return &pack{
-		name:        name,
-		idxMapping:  idxMapping,
-		idx:         idx,
-		dataMapping: dataMapping,
-		data:        dataMapping.Data(),
+		name:         name,
+		idxMapping:   idxMapping,
+		idx:          idx,
+		dataMapping:  dataMapping,
+		data:         dataMapping.Data(),
+		bloomMapping: bloomMapping,
+		filter:       filter,
 	}, nil
 }
 
+func openBloom(root *os.Root, name string, objectFormat id.ObjectFormat) (*mmap.Mmap, *bloom.Bloom) {
+	mapping, err := mapFile(root, name+".bloom")
+	if err != nil {
+		return nil, nil
+	}
+
+	filter, err := bloom.Parse(mapping.Data(), objectFormat)
+	if err != nil {
+		_ = mapping.Close()
+
+		return nil, nil
+	}
+
+	return mapping, &filter
+}
+
 // mapFile opens and maps one file under root.
 func mapFile(root *os.Root, name string) (*mmap.Mmap, error) {
 	file, err := root.Open(name)
@@ -125,10 +149,16 @@ func validatePackData(data []byte, idx *packidx.Packidx, hashSize int) error {
 	return nil
 }
 
-// close releases the pack data and index mappings.
+// close releases the pack data, index, and filter mappings.
 func (pack *pack) close() error {
-	return errors.Join(
+	errs := []error{
 		pack.dataMapping.Close(),
 		pack.idxMapping.Close(),
-	)
+	}
+
+	if pack.bloomMapping != nil {
+		errs = append(errs, pack.bloomMapping.Close())
+	}
+
+	return errors.Join(errs...)
 }