From d36dec9dc7019d67e0acf12c52607110cc0edc62 Mon Sep 17 00:00:00 2001
From: Luke Shumaker <lukeshu@lukeshu.com>
Date: Fri, 3 Feb 2023 19:10:08 -0700
Subject: Move sumrunwithgaps.go from btrfssum to rebuildmappings

---
 .../btrfsinspect/rebuildmappings/fuzzymatchsums.go |   2 +-
 .../btrfsinspect/rebuildmappings/logicalsums.go    |  14 +-
 .../btrfsinspect/rebuildmappings/matchsums.go      |   2 +-
 .../btrfsinspect/rebuildmappings/sumrunwithgaps.go | 161 +++++++++++++++++++++
 4 files changed, 170 insertions(+), 9 deletions(-)
 create mode 100644 lib/btrfsprogs/btrfsinspect/rebuildmappings/sumrunwithgaps.go

(limited to 'lib/btrfsprogs')

diff --git a/lib/btrfsprogs/btrfsinspect/rebuildmappings/fuzzymatchsums.go b/lib/btrfsprogs/btrfsinspect/rebuildmappings/fuzzymatchsums.go
index 9e6b864..b51526b 100644
--- a/lib/btrfsprogs/btrfsinspect/rebuildmappings/fuzzymatchsums.go
+++ b/lib/btrfsprogs/btrfsinspect/rebuildmappings/fuzzymatchsums.go
@@ -41,7 +41,7 @@ func fuzzyMatchBlockGroupSums(ctx context.Context,
 	fs *btrfs.FS,
 	blockgroups map[btrfsvol.LogicalAddr]BlockGroup,
 	physicalSums map[btrfsvol.DeviceID]btrfssum.SumRun[btrfsvol.PhysicalAddr],
-	logicalSums btrfssum.SumRunWithGaps[btrfsvol.LogicalAddr],
+	logicalSums SumRunWithGaps[btrfsvol.LogicalAddr],
 ) error {
 	_ctx := ctx
 
diff --git a/lib/btrfsprogs/btrfsinspect/rebuildmappings/logicalsums.go b/lib/btrfsprogs/btrfsinspect/rebuildmappings/logicalsums.go
index 537a970..69d14c7 100644
--- a/lib/btrfsprogs/btrfsinspect/rebuildmappings/logicalsums.go
+++ b/lib/btrfsprogs/btrfsinspect/rebuildmappings/logicalsums.go
@@ -1,4 +1,4 @@
-// Copyright (C) 2022  Luke Shumaker <lukeshu@lukeshu.com>
+// Copyright (C) 2022-2023  Luke Shumaker <lukeshu@lukeshu.com>
 //
 // SPDX-License-Identifier: GPL-2.0-or-later
 
@@ -20,7 +20,7 @@ import (
 	"git.lukeshu.com/btrfs-progs-ng/lib/slices"
 )
 
-func ExtractLogicalSums(ctx context.Context, scanResults btrfsinspect.ScanDevicesResult) btrfssum.SumRunWithGaps[btrfsvol.LogicalAddr] {
+func ExtractLogicalSums(ctx context.Context, scanResults btrfsinspect.ScanDevicesResult) SumRunWithGaps[btrfsvol.LogicalAddr] {
 	var records []btrfsinspect.SysExtentCSum
 	for _, devResults := range scanResults {
 		records = append(records, devResults.FoundExtentCSums...)
@@ -38,7 +38,7 @@ func ExtractLogicalSums(ctx context.Context, scanResults btrfsinspect.ScanDevice
 		}
 	})
 	if len(records) == 0 {
-		return btrfssum.SumRunWithGaps[btrfsvol.LogicalAddr]{}
+		return SumRunWithGaps[btrfsvol.LogicalAddr]{}
 	}
 	sumSize := records[0].Sums.ChecksumSize
 
@@ -149,7 +149,7 @@ func ExtractLogicalSums(ctx context.Context, scanResults btrfsinspect.ScanDevice
 	}
 
 	// Now flatten that RBTree in to a SumRunWithGaps.
-	var flattened btrfssum.SumRunWithGaps[btrfsvol.LogicalAddr]
+	var flattened SumRunWithGaps[btrfsvol.LogicalAddr]
 	var curAddr btrfsvol.LogicalAddr
 	var curSums strings.Builder
 	_ = addrspace.Walk(func(node *containers.RBNode[btrfsinspect.SysExtentCSum]) error {
@@ -183,7 +183,7 @@ func ExtractLogicalSums(ctx context.Context, scanResults btrfsinspect.ScanDevice
 	return flattened
 }
 
-func ListUnmappedLogicalRegions(fs *btrfs.FS, logicalSums btrfssum.SumRunWithGaps[btrfsvol.LogicalAddr]) []btrfssum.SumRun[btrfsvol.LogicalAddr] {
+func ListUnmappedLogicalRegions(fs *btrfs.FS, logicalSums SumRunWithGaps[btrfsvol.LogicalAddr]) []btrfssum.SumRun[btrfsvol.LogicalAddr] {
 	// There are a lot of ways this algorithm could be made
 	// faster.
 	var ret []btrfssum.SumRun[btrfsvol.LogicalAddr]
@@ -226,8 +226,8 @@ func ListUnmappedLogicalRegions(fs *btrfs.FS, logicalSums btrfssum.SumRunWithGap
 	return ret
 }
 
-func SumsForLogicalRegion(sums btrfssum.SumRunWithGaps[btrfsvol.LogicalAddr], beg btrfsvol.LogicalAddr, size btrfsvol.AddrDelta) btrfssum.SumRunWithGaps[btrfsvol.LogicalAddr] {
-	runs := btrfssum.SumRunWithGaps[btrfsvol.LogicalAddr]{
+func SumsForLogicalRegion(sums SumRunWithGaps[btrfsvol.LogicalAddr], beg btrfsvol.LogicalAddr, size btrfsvol.AddrDelta) SumRunWithGaps[btrfsvol.LogicalAddr] {
+	runs := SumRunWithGaps[btrfsvol.LogicalAddr]{
 		Addr: beg,
 		Size: size,
 	}
diff --git a/lib/btrfsprogs/btrfsinspect/rebuildmappings/matchsums.go b/lib/btrfsprogs/btrfsinspect/rebuildmappings/matchsums.go
index 02c657f..c38314a 100644
--- a/lib/btrfsprogs/btrfsinspect/rebuildmappings/matchsums.go
+++ b/lib/btrfsprogs/btrfsinspect/rebuildmappings/matchsums.go
@@ -22,7 +22,7 @@ func matchBlockGroupSums(ctx context.Context,
 	fs *btrfs.FS,
 	blockgroups map[btrfsvol.LogicalAddr]BlockGroup,
 	physicalSums map[btrfsvol.DeviceID]btrfssum.SumRun[btrfsvol.PhysicalAddr],
-	logicalSums btrfssum.SumRunWithGaps[btrfsvol.LogicalAddr],
+	logicalSums SumRunWithGaps[btrfsvol.LogicalAddr],
 ) error {
 	regions := ListUnmappedPhysicalRegions(fs)
 	numBlockgroups := len(blockgroups)
diff --git a/lib/btrfsprogs/btrfsinspect/rebuildmappings/sumrunwithgaps.go b/lib/btrfsprogs/btrfsinspect/rebuildmappings/sumrunwithgaps.go
new file mode 100644
index 0000000..8c1f3ed
--- /dev/null
+++ b/lib/btrfsprogs/btrfsinspect/rebuildmappings/sumrunwithgaps.go
@@ -0,0 +1,161 @@
+// Copyright (C) 2022-2023  Luke Shumaker <lukeshu@lukeshu.com>
+//
+// SPDX-License-Identifier: GPL-2.0-or-later
+
+package rebuildmappings
+
+import (
+	"context"
+	"fmt"
+	"io"
+	"math"
+
+	"git.lukeshu.com/go/lowmemjson"
+
+	"git.lukeshu.com/btrfs-progs-ng/lib/btrfs/btrfssum"
+	"git.lukeshu.com/btrfs-progs-ng/lib/btrfs/btrfsvol"
+	"git.lukeshu.com/btrfs-progs-ng/lib/diskio"
+)
+
+type SumRunWithGaps[Addr btrfsvol.IntAddr[Addr]] struct {
+	// Store the start address and size, in order to facilitate
+	// leading and trailing gaps.
+	Addr Addr
+	Size btrfsvol.AddrDelta
+
+	Runs []btrfssum.SumRun[Addr]
+}
+
+var (
+	_ lowmemjson.Encodable = SumRunWithGaps[btrfsvol.LogicalAddr]{}
+	_ lowmemjson.Decodable = (*SumRunWithGaps[btrfsvol.LogicalAddr])(nil)
+)
+
+func (sg SumRunWithGaps[Addr]) NumSums() int {
+	return int(sg.Size / btrfssum.BlockSize)
+}
+
+func (sg SumRunWithGaps[Addr]) PctFull() float64 {
+	total := sg.NumSums()
+	var full int
+	for _, run := range sg.Runs {
+		full += run.NumSums()
+	}
+	return float64(full) / float64(total)
+}
+
+func (sg SumRunWithGaps[Addr]) RunForAddr(addr Addr) (btrfssum.SumRun[Addr], Addr, bool) {
+	for _, run := range sg.Runs {
+		if run.Addr > addr {
+			return btrfssum.SumRun[Addr]{}, run.Addr, false
+		}
+		if run.Addr.Add(run.Size()) <= addr {
+			continue
+		}
+		return run, 0, true
+	}
+	return btrfssum.SumRun[Addr]{}, math.MaxInt64, false
+}
+
+func (sg SumRunWithGaps[Addr]) SumForAddr(addr Addr) (btrfssum.ShortSum, error) {
+	if addr < sg.Addr || addr >= sg.Addr.Add(sg.Size) {
+		return "", io.EOF
+	}
+	for _, run := range sg.Runs {
+		if run.Addr > addr {
+			return "", diskio.ErrWildcard
+		}
+		if run.Addr.Add(run.Size()) <= addr {
+			continue
+		}
+		off := int((addr-run.Addr)/btrfssum.BlockSize) * run.ChecksumSize
+		return run.Sums[off : off+run.ChecksumSize], nil
+	}
+	return "", diskio.ErrWildcard
+}
+
+func (sg SumRunWithGaps[Addr]) Walk(ctx context.Context, fn func(Addr, btrfssum.ShortSum) error) error {
+	for _, run := range sg.Runs {
+		if err := run.Walk(ctx, fn); err != nil {
+			return err
+		}
+	}
+	return nil
+}
+
+// Get implements diskio.Sequence[int, ShortSum]
+func (sg SumRunWithGaps[Addr]) Get(sumIdx int64) (btrfssum.ShortSum, error) {
+	addr := sg.Addr.Add(btrfsvol.AddrDelta(sumIdx) * btrfssum.BlockSize)
+	return sg.SumForAddr(addr)
+}
+
+func (sg SumRunWithGaps[Addr]) EncodeJSON(w io.Writer) error {
+	if _, err := fmt.Fprintf(w, `{"Addr":%d,"Size":%d,"Runs":[`, sg.Addr, sg.Size); err != nil {
+		return err
+	}
+	cur := sg.Addr
+	for i, run := range sg.Runs {
+		if i > 0 {
+			if _, err := w.Write([]byte{','}); err != nil {
+				return err
+			}
+		}
+		switch {
+		case run.Addr < cur:
+			return fmt.Errorf("invalid %T: addr went backwards: %v < %v", sg, run.Addr, cur)
+		case run.Addr > cur:
+			if _, err := fmt.Fprintf(w, `{"Gap":%d},`, run.Addr.Sub(cur)); err != nil {
+				return err
+			}
+			fallthrough
+		default:
+			if err := lowmemjson.NewEncoder(w).Encode(run); err != nil {
+				return err
+			}
+			cur = run.Addr.Add(run.Size())
+		}
+	}
+	end := sg.Addr.Add(sg.Size)
+	switch {
+	case end < cur:
+		return fmt.Errorf("invalid %T: addr went backwards: %v < %v", sg, end, cur)
+	case end > cur:
+		if _, err := fmt.Fprintf(w, `,{"Gap":%d}`, end.Sub(cur)); err != nil {
+			return err
+		}
+	}
+	if _, err := w.Write([]byte("]}")); err != nil {
+		return err
+	}
+	return nil
+}
+
+func (sg *SumRunWithGaps[Addr]) DecodeJSON(r io.RuneScanner) error {
+	*sg = SumRunWithGaps[Addr]{}
+	var name string
+	return lowmemjson.DecodeObject(r,
+		func(r io.RuneScanner) error {
+			return lowmemjson.NewDecoder(r).Decode(&name)
+		},
+		func(r io.RuneScanner) error {
+			switch name {
+			case "Addr":
+				return lowmemjson.NewDecoder(r).Decode(&sg.Addr)
+			case "Size":
+				return lowmemjson.NewDecoder(r).Decode(&sg.Size)
+			case "Runs":
+				return lowmemjson.DecodeArray(r, func(r io.RuneScanner) error {
+					var run btrfssum.SumRun[Addr]
+					if err := lowmemjson.NewDecoder(r).Decode(&run); err != nil {
+						return err
+					}
+					if run.ChecksumSize > 0 {
+						sg.Runs = append(sg.Runs, run)
+					}
+					return nil
+				})
+			default:
+				return fmt.Errorf("unknown key %q", name)
+			}
+		})
+}
-- 
cgit v1.2.3-2-g168b


From 77f3c0d7cd21274d00984b72dfce05394d11bdd0 Mon Sep 17 00:00:00 2001
From: Luke Shumaker <lukeshu@lukeshu.com>
Date: Fri, 3 Feb 2023 19:13:22 -0700
Subject: Move KMP IndexAll from diskio to rebuildmappings

---
 lib/btrfsprogs/btrfsinspect/rebuildmappings/kmp.go | 149 +++++++++++++++++++++
 .../btrfsinspect/rebuildmappings/kmp_test.go       | 126 +++++++++++++++++
 .../btrfsinspect/rebuildmappings/matchsums.go      |   3 +-
 .../btrfsinspect/rebuildmappings/sumrunwithgaps.go |   5 +-
 ...6820e3f98383aebadd2af3a22aa248546a228b08451c30d |   3 +
 ...14e1f3425bfa6ccd6bfd42824a26e8cbd63b5117934e600 |   3 +
 ...293dbf423c1a816b697e2763a29d7c37aa476d6eef6fd60 |   3 +
 ...3b8e08d58d0f69cc22aefb12fd9b5931e49ff0e41953738 |   3 +
 ...7d7b2fc0237d369082a6bf5dfe39e05c113b42ff6218d5d |   3 +
 9 files changed, 293 insertions(+), 5 deletions(-)
 create mode 100644 lib/btrfsprogs/btrfsinspect/rebuildmappings/kmp.go
 create mode 100644 lib/btrfsprogs/btrfsinspect/rebuildmappings/kmp_test.go
 create mode 100644 lib/btrfsprogs/btrfsinspect/rebuildmappings/testdata/fuzz/FuzzIndexAll/593a5dd328ee86bac6820e3f98383aebadd2af3a22aa248546a228b08451c30d
 create mode 100644 lib/btrfsprogs/btrfsinspect/rebuildmappings/testdata/fuzz/FuzzIndexAll/6bd9babbebf7eb78814e1f3425bfa6ccd6bfd42824a26e8cbd63b5117934e600
 create mode 100644 lib/btrfsprogs/btrfsinspect/rebuildmappings/testdata/fuzz/FuzzIndexAll/84ed65595ad05a58e293dbf423c1a816b697e2763a29d7c37aa476d6eef6fd60
 create mode 100644 lib/btrfsprogs/btrfsinspect/rebuildmappings/testdata/fuzz/FuzzIndexAll/9be40f71bc49b1b5c3b8e08d58d0f69cc22aefb12fd9b5931e49ff0e41953738
 create mode 100644 lib/btrfsprogs/btrfsinspect/rebuildmappings/testdata/fuzz/FuzzIndexAll/e43317ec61b0da9627d7b2fc0237d369082a6bf5dfe39e05c113b42ff6218d5d

(limited to 'lib/btrfsprogs')

diff --git a/lib/btrfsprogs/btrfsinspect/rebuildmappings/kmp.go b/lib/btrfsprogs/btrfsinspect/rebuildmappings/kmp.go
new file mode 100644
index 0000000..eeaab0c
--- /dev/null
+++ b/lib/btrfsprogs/btrfsinspect/rebuildmappings/kmp.go
@@ -0,0 +1,149 @@
+// Copyright (C) 2022-2023  Luke Shumaker <lukeshu@lukeshu.com>
+//
+// SPDX-License-Identifier: GPL-2.0-or-later
+
+package rebuildmappings
+
+import (
+	"errors"
+	"io"
+
+	"git.lukeshu.com/btrfs-progs-ng/lib/diskio"
+)
+
+var ErrWildcard = errors.New("wildcard")
+
+func kmpEq2[K ~int64, V comparable](aS diskio.Sequence[K, V], aI K, bS diskio.Sequence[K, V], bI K) bool {
+	aV, aErr := aS.Get(aI)
+	bV, bErr := bS.Get(bI)
+	if aErr != nil {
+		//nolint:errorlint // The == is just a fast-path; we still fall back to errors.Is.
+		if aErr == ErrWildcard || errors.Is(aErr, ErrWildcard) {
+			aV = bV
+			aErr = nil
+		} else {
+			panic(aErr)
+		}
+	}
+	if bErr != nil {
+		//nolint:errorlint // The == is just a fast-path; we still fall back to errors.Is.
+		if bErr == ErrWildcard || errors.Is(bErr, ErrWildcard) {
+			bV = aV
+			bErr = nil
+		} else {
+			panic(bErr)
+		}
+	}
+	if aErr != nil || bErr != nil {
+		return false
+	}
+	return aV == bV
+}
+
+func kmpEq1[K ~int64, V comparable](aV V, bS diskio.Sequence[K, V], bI K) bool {
+	bV, bErr := bS.Get(bI)
+	if bErr != nil {
+		//nolint:errorlint // The == is just a fast-path; we still fall back to errors.Is.
+		if bErr == ErrWildcard || errors.Is(bErr, ErrWildcard) {
+			return true
+		}
+		panic(bErr)
+	}
+	return aV == bV
+}
+
+// buildKMPTable takes the string 'substr', and returns a table such
+// that 'table[matchLen-1]' is the largest value 'val' for which 'val < matchLen' and
+// 'substr[:val] == substr[matchLen-val:matchLen]'.
+func buildKMPTable[K ~int64, V comparable](substr diskio.Sequence[K, V]) ([]K, error) {
+	var substrLen K
+	for {
+		//nolint:errorlint // The == is just a fast-path; we still fall back to errors.Is.
+		if _, err := substr.Get(substrLen); err != nil && !(err == ErrWildcard || errors.Is(err, ErrWildcard)) {
+			if errors.Is(err, io.EOF) {
+				break
+			}
+			return nil, err
+		}
+		substrLen++
+	}
+
+	table := make([]K, substrLen)
+	for j := K(0); j < substrLen; j++ {
+		if j == 0 {
+			// First entry must always be 0 (in order to
+			// satisfy 'val < matchLen').
+			continue
+		}
+		val := table[j-1]
+		// not a match; go back
+		for val > 0 && !kmpEq2(substr, j, substr, val) {
+			val = table[val-1]
+		}
+		// is a match; go forward
+		if kmpEq2(substr, val, substr, j) {
+			val++
+		}
+		table[j] = val
+	}
+	return table, nil
+}
+
+// IndexAll returns the starting-position of all possibly-overlapping
+// occurrences of 'substr' in the 'str' sequence.
+//
+// Will hop around in 'substr', but will only get the natural sequence
+// [0...) in order from 'str'.  When hopping around in 'substr' it
+// assumes that once it has gotten a given index without error, it can
+// continue to do so without error; errors appearing later will cause
+// panics.
+//
+// Will panic if the length of 'substr' is 0.
+//
+// The 'substr' may include wildcard characters by returning
+// ErrWildcard for a position.
+//
+// Uses the Knuth-Morris-Pratt algorithm.
+func IndexAll[K ~int64, V comparable](str, substr diskio.Sequence[K, V]) ([]K, error) {
+	table, err := buildKMPTable(substr)
+	if err != nil {
+		return nil, err
+	}
+	substrLen := K(len(table))
+	if substrLen == 0 {
+		panic(errors.New("rebuildmappings.IndexAll: empty substring"))
+	}
+
+	var matches []K
+	var curMatchBeg K
+	var curMatchLen K
+
+	for pos := K(0); ; pos++ {
+		chr, err := str.Get(pos)
+		if err != nil {
+			if errors.Is(err, io.EOF) {
+				err = nil
+			}
+			return matches, err
+		}
+
+		// Consider 'chr'
+		for curMatchLen > 0 && !kmpEq1(chr, substr, curMatchLen) { // shorten the match
+			overlap := table[curMatchLen-1]
+			curMatchBeg += curMatchLen - overlap
+			curMatchLen = overlap
+		}
+		if kmpEq1(chr, substr, curMatchLen) { // lengthen the match
+			if curMatchLen == 0 {
+				curMatchBeg = pos
+			}
+			curMatchLen++
+			if curMatchLen == substrLen {
+				matches = append(matches, curMatchBeg)
+				overlap := table[curMatchLen-1]
+				curMatchBeg += curMatchLen - overlap
+				curMatchLen = overlap
+			}
+		}
+	}
+}
diff --git a/lib/btrfsprogs/btrfsinspect/rebuildmappings/kmp_test.go b/lib/btrfsprogs/btrfsinspect/rebuildmappings/kmp_test.go
new file mode 100644
index 0000000..910452a
--- /dev/null
+++ b/lib/btrfsprogs/btrfsinspect/rebuildmappings/kmp_test.go
@@ -0,0 +1,126 @@
+// Copyright (C) 2022-2023  Luke Shumaker <lukeshu@lukeshu.com>
+//
+// SPDX-License-Identifier: GPL-2.0-or-later
+
+package rebuildmappings
+
+import (
+	"bytes"
+	"io"
+	"testing"
+
+	"github.com/stretchr/testify/assert"
+	"github.com/stretchr/testify/require"
+
+	"git.lukeshu.com/btrfs-progs-ng/lib/diskio"
+)
+
+func TestBuildKMPTable(t *testing.T) {
+	t.Parallel()
+	substr := diskio.SliceSequence[int64, byte]([]byte("ababaa"))
+	table, err := buildKMPTable[int64, byte](substr)
+	require.NoError(t, err)
+	require.Equal(t,
+		[]int64{0, 0, 1, 2, 3, 1},
+		table)
+	for j, val := range table {
+		matchLen := j + 1
+		assert.Equalf(t, substr[:val], substr[matchLen-int(val):matchLen],
+			"for table[%d]=%d", j, val)
+	}
+}
+
+func FuzzBuildKMPTable(f *testing.F) {
+	f.Add([]byte("ababaa"))
+	f.Fuzz(func(t *testing.T, substr []byte) {
+		table, err := buildKMPTable[int64, byte](diskio.SliceSequence[int64, byte](substr))
+		require.NoError(t, err)
+		require.Equal(t, len(substr), len(table), "length")
+		for j, val := range table {
+			matchLen := j + 1
+			assert.Equalf(t, substr[:val], substr[matchLen-int(val):matchLen],
+				"for table[%d]=%d", j, val)
+		}
+	})
+}
+
+func NaiveIndexAll(str, substr []byte) []int64 {
+	var matches []int64
+	for i := range str {
+		if bytes.HasPrefix(str[i:], substr) {
+			matches = append(matches, int64(i))
+		}
+	}
+	return matches
+}
+
+func FuzzIndexAll(f *testing.F) {
+	f.Fuzz(func(t *testing.T, str, substr []byte) {
+		if len(substr) == 0 {
+			t.Skip()
+		}
+		t.Logf("str   =%q", str)
+		t.Logf("substr=%q", substr)
+		exp := NaiveIndexAll(str, substr)
+		act, err := IndexAll[int64, byte](
+			&diskio.ByteReaderSequence[int64]{R: bytes.NewReader(str)},
+			diskio.SliceSequence[int64, byte](substr))
+		assert.NoError(t, err)
+		assert.Equal(t, exp, act)
+	})
+}
+
+type RESeq string
+
+func (re RESeq) Get(i int64) (byte, error) {
+	if i < 0 || i >= int64(len(re)) {
+		return 0, io.EOF
+	}
+	chr := re[int(i)]
+	if chr == '.' {
+		return 0, ErrWildcard
+	}
+	return chr, nil
+}
+
+func TestKMPWildcard(t *testing.T) {
+	t.Parallel()
+	type testcase struct {
+		InStr      string
+		InSubstr   string
+		ExpMatches []int64
+	}
+	testcases := map[string]testcase{
+		"trivial-bar": {
+			InStr:      "foo_bar",
+			InSubstr:   "foo.ba.",
+			ExpMatches: []int64{0},
+		},
+		"trival-baz": {
+			InStr:      "foo-baz",
+			InSubstr:   "foo.ba.",
+			ExpMatches: []int64{0},
+		},
+		"suffix": {
+			InStr:      "foobarbaz",
+			InSubstr:   "...baz",
+			ExpMatches: []int64{3},
+		},
+		"overlap": {
+			InStr:      "foobarbar",
+			InSubstr:   "...bar",
+			ExpMatches: []int64{0, 3},
+		},
+	}
+	for tcName, tc := range testcases {
+		tc := tc
+		t.Run(tcName, func(t *testing.T) {
+			t.Parallel()
+			matches, err := IndexAll[int64, byte](
+				diskio.StringSequence[int64](tc.InStr),
+				RESeq(tc.InSubstr))
+			assert.NoError(t, err)
+			assert.Equal(t, tc.ExpMatches, matches)
+		})
+	}
+}
diff --git a/lib/btrfsprogs/btrfsinspect/rebuildmappings/matchsums.go b/lib/btrfsprogs/btrfsinspect/rebuildmappings/matchsums.go
index c38314a..eda37bd 100644
--- a/lib/btrfsprogs/btrfsinspect/rebuildmappings/matchsums.go
+++ b/lib/btrfsprogs/btrfsinspect/rebuildmappings/matchsums.go
@@ -14,7 +14,6 @@ import (
 	"git.lukeshu.com/btrfs-progs-ng/lib/btrfs/btrfssum"
 	"git.lukeshu.com/btrfs-progs-ng/lib/btrfs/btrfsvol"
 	"git.lukeshu.com/btrfs-progs-ng/lib/containers"
-	"git.lukeshu.com/btrfs-progs-ng/lib/diskio"
 	"git.lukeshu.com/btrfs-progs-ng/lib/maps"
 )
 
@@ -37,7 +36,7 @@ func matchBlockGroupSums(ctx context.Context,
 
 		var matches []btrfsvol.QualifiedPhysicalAddr
 		if err := WalkUnmappedPhysicalRegions(ctx, physicalSums, regions, func(devID btrfsvol.DeviceID, region btrfssum.SumRun[btrfsvol.PhysicalAddr]) error {
-			rawMatches, err := diskio.IndexAll[int64, btrfssum.ShortSum](region, bgRun)
+			rawMatches, err := IndexAll[int64, btrfssum.ShortSum](region, bgRun)
 			if err != nil {
 				return err
 			}
diff --git a/lib/btrfsprogs/btrfsinspect/rebuildmappings/sumrunwithgaps.go b/lib/btrfsprogs/btrfsinspect/rebuildmappings/sumrunwithgaps.go
index 8c1f3ed..d1064d8 100644
--- a/lib/btrfsprogs/btrfsinspect/rebuildmappings/sumrunwithgaps.go
+++ b/lib/btrfsprogs/btrfsinspect/rebuildmappings/sumrunwithgaps.go
@@ -14,7 +14,6 @@ import (
 
 	"git.lukeshu.com/btrfs-progs-ng/lib/btrfs/btrfssum"
 	"git.lukeshu.com/btrfs-progs-ng/lib/btrfs/btrfsvol"
-	"git.lukeshu.com/btrfs-progs-ng/lib/diskio"
 )
 
 type SumRunWithGaps[Addr btrfsvol.IntAddr[Addr]] struct {
@@ -63,7 +62,7 @@ func (sg SumRunWithGaps[Addr]) SumForAddr(addr Addr) (btrfssum.ShortSum, error)
 	}
 	for _, run := range sg.Runs {
 		if run.Addr > addr {
-			return "", diskio.ErrWildcard
+			return "", ErrWildcard
 		}
 		if run.Addr.Add(run.Size()) <= addr {
 			continue
@@ -71,7 +70,7 @@ func (sg SumRunWithGaps[Addr]) SumForAddr(addr Addr) (btrfssum.ShortSum, error)
 		off := int((addr-run.Addr)/btrfssum.BlockSize) * run.ChecksumSize
 		return run.Sums[off : off+run.ChecksumSize], nil
 	}
-	return "", diskio.ErrWildcard
+	return "", ErrWildcard
 }
 
 func (sg SumRunWithGaps[Addr]) Walk(ctx context.Context, fn func(Addr, btrfssum.ShortSum) error) error {
diff --git a/lib/btrfsprogs/btrfsinspect/rebuildmappings/testdata/fuzz/FuzzIndexAll/593a5dd328ee86bac6820e3f98383aebadd2af3a22aa248546a228b08451c30d b/lib/btrfsprogs/btrfsinspect/rebuildmappings/testdata/fuzz/FuzzIndexAll/593a5dd328ee86bac6820e3f98383aebadd2af3a22aa248546a228b08451c30d
new file mode 100644
index 0000000..9d14adf
--- /dev/null
+++ b/lib/btrfsprogs/btrfsinspect/rebuildmappings/testdata/fuzz/FuzzIndexAll/593a5dd328ee86bac6820e3f98383aebadd2af3a22aa248546a228b08451c30d
@@ -0,0 +1,3 @@
+go test fuzz v1
+[]byte("0")
+[]byte("1")
diff --git a/lib/btrfsprogs/btrfsinspect/rebuildmappings/testdata/fuzz/FuzzIndexAll/6bd9babbebf7eb78814e1f3425bfa6ccd6bfd42824a26e8cbd63b5117934e600 b/lib/btrfsprogs/btrfsinspect/rebuildmappings/testdata/fuzz/FuzzIndexAll/6bd9babbebf7eb78814e1f3425bfa6ccd6bfd42824a26e8cbd63b5117934e600
new file mode 100644
index 0000000..269f061
--- /dev/null
+++ b/lib/btrfsprogs/btrfsinspect/rebuildmappings/testdata/fuzz/FuzzIndexAll/6bd9babbebf7eb78814e1f3425bfa6ccd6bfd42824a26e8cbd63b5117934e600
@@ -0,0 +1,3 @@
+go test fuzz v1
+[]byte("0")
+[]byte("0")
diff --git a/lib/btrfsprogs/btrfsinspect/rebuildmappings/testdata/fuzz/FuzzIndexAll/84ed65595ad05a58e293dbf423c1a816b697e2763a29d7c37aa476d6eef6fd60 b/lib/btrfsprogs/btrfsinspect/rebuildmappings/testdata/fuzz/FuzzIndexAll/84ed65595ad05a58e293dbf423c1a816b697e2763a29d7c37aa476d6eef6fd60
new file mode 100644
index 0000000..b8f1562
--- /dev/null
+++ b/lib/btrfsprogs/btrfsinspect/rebuildmappings/testdata/fuzz/FuzzIndexAll/84ed65595ad05a58e293dbf423c1a816b697e2763a29d7c37aa476d6eef6fd60
@@ -0,0 +1,3 @@
+go test fuzz v1
+[]byte("0")
+[]byte("")
diff --git a/lib/btrfsprogs/btrfsinspect/rebuildmappings/testdata/fuzz/FuzzIndexAll/9be40f71bc49b1b5c3b8e08d58d0f69cc22aefb12fd9b5931e49ff0e41953738 b/lib/btrfsprogs/btrfsinspect/rebuildmappings/testdata/fuzz/FuzzIndexAll/9be40f71bc49b1b5c3b8e08d58d0f69cc22aefb12fd9b5931e49ff0e41953738
new file mode 100644
index 0000000..be67506
--- /dev/null
+++ b/lib/btrfsprogs/btrfsinspect/rebuildmappings/testdata/fuzz/FuzzIndexAll/9be40f71bc49b1b5c3b8e08d58d0f69cc22aefb12fd9b5931e49ff0e41953738
@@ -0,0 +1,3 @@
+go test fuzz v1
+[]byte("\xde\xdb!")
+[]byte("\xde\xdb")
diff --git a/lib/btrfsprogs/btrfsinspect/rebuildmappings/testdata/fuzz/FuzzIndexAll/e43317ec61b0da9627d7b2fc0237d369082a6bf5dfe39e05c113b42ff6218d5d b/lib/btrfsprogs/btrfsinspect/rebuildmappings/testdata/fuzz/FuzzIndexAll/e43317ec61b0da9627d7b2fc0237d369082a6bf5dfe39e05c113b42ff6218d5d
new file mode 100644
index 0000000..c3bfa37
--- /dev/null
+++ b/lib/btrfsprogs/btrfsinspect/rebuildmappings/testdata/fuzz/FuzzIndexAll/e43317ec61b0da9627d7b2fc0237d369082a6bf5dfe39e05c113b42ff6218d5d
@@ -0,0 +1,3 @@
+go test fuzz v1
+[]byte("\x10\x10\x15")
+[]byte("\x10\x15")
-- 
cgit v1.2.3-2-g168b


From ef60daef395b20b67042c011f5b2a1131049e275 Mon Sep 17 00:00:00 2001
From: Luke Shumaker <lukeshu@lukeshu.com>
Date: Fri, 3 Feb 2023 19:50:35 -0700
Subject: rebuildmappings: Optimize the KMP search

---
 .../btrfsinspect/rebuildmappings/fuzzymatchsums.go |   2 +-
 lib/btrfsprogs/btrfsinspect/rebuildmappings/kmp.go | 106 +++++++--------------
 .../btrfsinspect/rebuildmappings/kmp_test.go       |  52 +++++-----
 .../btrfsinspect/rebuildmappings/matchsums.go      |   5 +-
 .../rebuildmappings/rebuildmappings.go             |   4 -
 .../btrfsinspect/rebuildmappings/sumrunwithgaps.go |  21 ++--
 6 files changed, 74 insertions(+), 116 deletions(-)

(limited to 'lib/btrfsprogs')

diff --git a/lib/btrfsprogs/btrfsinspect/rebuildmappings/fuzzymatchsums.go b/lib/btrfsprogs/btrfsinspect/rebuildmappings/fuzzymatchsums.go
index b51526b..6b75d84 100644
--- a/lib/btrfsprogs/btrfsinspect/rebuildmappings/fuzzymatchsums.go
+++ b/lib/btrfsprogs/btrfsinspect/rebuildmappings/fuzzymatchsums.go
@@ -69,7 +69,7 @@ func fuzzyMatchBlockGroupSums(ctx context.Context,
 		blockgroup := blockgroups[bgLAddr]
 		bgRun := SumsForLogicalRegion(logicalSums, blockgroup.LAddr, blockgroup.Size)
 
-		d := bgRun.NumSums()
+		d := bgRun.PatLen()
 		matches := make(map[btrfsvol.QualifiedPhysicalAddr]int)
 		if err := bgRun.Walk(ctx, func(laddr btrfsvol.LogicalAddr, sum btrfssum.ShortSum) error { // O(n*…
 			off := laddr.Sub(bgRun.Addr)
diff --git a/lib/btrfsprogs/btrfsinspect/rebuildmappings/kmp.go b/lib/btrfsprogs/btrfsinspect/rebuildmappings/kmp.go
index eeaab0c..20772ba 100644
--- a/lib/btrfsprogs/btrfsinspect/rebuildmappings/kmp.go
+++ b/lib/btrfsprogs/btrfsinspect/rebuildmappings/kmp.go
@@ -6,48 +6,24 @@ package rebuildmappings
 
 import (
 	"errors"
-	"io"
 
 	"git.lukeshu.com/btrfs-progs-ng/lib/diskio"
 )
 
-var ErrWildcard = errors.New("wildcard")
-
-func kmpEq2[K ~int64, V comparable](aS diskio.Sequence[K, V], aI K, bS diskio.Sequence[K, V], bI K) bool {
-	aV, aErr := aS.Get(aI)
-	bV, bErr := bS.Get(bI)
-	if aErr != nil {
-		//nolint:errorlint // The == is just a fast-path; we still fall back to errors.Is.
-		if aErr == ErrWildcard || errors.Is(aErr, ErrWildcard) {
-			aV = bV
-			aErr = nil
-		} else {
-			panic(aErr)
-		}
-	}
-	if bErr != nil {
-		//nolint:errorlint // The == is just a fast-path; we still fall back to errors.Is.
-		if bErr == ErrWildcard || errors.Is(bErr, ErrWildcard) {
-			bV = aV
-			bErr = nil
-		} else {
-			panic(bErr)
-		}
-	}
-	if aErr != nil || bErr != nil {
-		return false
-	}
-	return aV == bV
+type kmpPattern[K ~int64 | ~int, V comparable] interface {
+	PatLen() K
+	// Get the value at 'pos' in the sequence.  Positions start at
+	// 0 and increment naturally.  It is invalid to call Get(pos)
+	// with a pos that is >= Len().  If there is a gap/wildcard at
+	// pos, ok is false.
+	PatGet(pos K) (v V, ok bool)
 }
 
-func kmpEq1[K ~int64, V comparable](aV V, bS diskio.Sequence[K, V], bI K) bool {
-	bV, bErr := bS.Get(bI)
-	if bErr != nil {
-		//nolint:errorlint // The == is just a fast-path; we still fall back to errors.Is.
-		if bErr == ErrWildcard || errors.Is(bErr, ErrWildcard) {
-			return true
-		}
-		panic(bErr)
+func kmpSelfEq[K ~int64 | ~int, V comparable](s kmpPattern[K, V], aI K, bI K) bool {
+	aV, aOK := s.PatGet(aI)
+	bV, bOK := s.PatGet(bI)
+	if !aOK || !bOK {
+		return true
 	}
 	return aV == bV
 }
@@ -55,18 +31,8 @@ func kmpEq1[K ~int64, V comparable](aV V, bS diskio.Sequence[K, V], bI K) bool {
 // buildKMPTable takes the string 'substr', and returns a table such
 // that 'table[matchLen-1]' is the largest value 'val' for which 'val < matchLen' and
 // 'substr[:val] == substr[matchLen-val:matchLen]'.
-func buildKMPTable[K ~int64, V comparable](substr diskio.Sequence[K, V]) ([]K, error) {
-	var substrLen K
-	for {
-		//nolint:errorlint // The == is just a fast-path; we still fall back to errors.Is.
-		if _, err := substr.Get(substrLen); err != nil && !(err == ErrWildcard || errors.Is(err, ErrWildcard)) {
-			if errors.Is(err, io.EOF) {
-				break
-			}
-			return nil, err
-		}
-		substrLen++
-	}
+func buildKMPTable[K ~int64 | ~int, V comparable](substr kmpPattern[K, V]) []K {
+	substrLen := substr.PatLen()
 
 	table := make([]K, substrLen)
 	for j := K(0); j < substrLen; j++ {
@@ -77,26 +43,31 @@ func buildKMPTable[K ~int64, V comparable](substr diskio.Sequence[K, V]) ([]K, e
 		}
 		val := table[j-1]
 		// not a match; go back
-		for val > 0 && !kmpEq2(substr, j, substr, val) {
+		for val > 0 && !kmpSelfEq(substr, j, val) {
 			val = table[val-1]
 		}
 		// is a match; go forward
-		if kmpEq2(substr, val, substr, j) {
+		if kmpSelfEq(substr, val, j) {
 			val++
 		}
 		table[j] = val
 	}
-	return table, nil
+	return table
 }
 
-// IndexAll returns the starting-position of all possibly-overlapping
+func kmpEq[K ~int64 | ~int, V comparable](aV V, bS kmpPattern[K, V], bI K) bool {
+	bV, ok := bS.PatGet(bI)
+	if !ok {
+		return true
+	}
+	return aV == bV
+}
+
+// indexAll returns the starting-position of all possibly-overlapping
 // occurrences of 'substr' in the 'str' sequence.
 //
 // Will hop around in 'substr', but will only get the natural sequence
-// [0...) in order from 'str'.  When hopping around in 'substr' it
-// assumes that once it has gotten a given index without error, it can
-// continue to do so without error; errors appearing later will cause
-// panics.
+// [0...) in order from 'str'.
 //
 // Will panic if the length of 'substr' is 0.
 //
@@ -104,11 +75,8 @@ func buildKMPTable[K ~int64, V comparable](substr diskio.Sequence[K, V]) ([]K, e
 // ErrWildcard for a position.
 //
 // Uses the Knuth-Morris-Pratt algorithm.
-func IndexAll[K ~int64, V comparable](str, substr diskio.Sequence[K, V]) ([]K, error) {
-	table, err := buildKMPTable(substr)
-	if err != nil {
-		return nil, err
-	}
+func indexAll[K ~int64 | ~int, V comparable](str diskio.Sequence[K, V], substr kmpPattern[K, V]) []K {
+	table := buildKMPTable(substr)
 	substrLen := K(len(table))
 	if substrLen == 0 {
 		panic(errors.New("rebuildmappings.IndexAll: empty substring"))
@@ -118,22 +86,17 @@ func IndexAll[K ~int64, V comparable](str, substr diskio.Sequence[K, V]) ([]K, e
 	var curMatchBeg K
 	var curMatchLen K
 
-	for pos := K(0); ; pos++ {
-		chr, err := str.Get(pos)
-		if err != nil {
-			if errors.Is(err, io.EOF) {
-				err = nil
-			}
-			return matches, err
-		}
+	strLen := str.SeqLen()
+	for pos := K(0); pos < strLen; pos++ {
+		chr := str.SeqGet(pos)
 
 		// Consider 'chr'
-		for curMatchLen > 0 && !kmpEq1(chr, substr, curMatchLen) { // shorten the match
+		for curMatchLen > 0 && !kmpEq(chr, substr, curMatchLen) { // shorten the match
 			overlap := table[curMatchLen-1]
 			curMatchBeg += curMatchLen - overlap
 			curMatchLen = overlap
 		}
-		if kmpEq1(chr, substr, curMatchLen) { // lengthen the match
+		if kmpEq(chr, substr, curMatchLen) { // lengthen the match
 			if curMatchLen == 0 {
 				curMatchBeg = pos
 			}
@@ -146,4 +109,5 @@ func IndexAll[K ~int64, V comparable](str, substr diskio.Sequence[K, V]) ([]K, e
 			}
 		}
 	}
+	return matches
 }
diff --git a/lib/btrfsprogs/btrfsinspect/rebuildmappings/kmp_test.go b/lib/btrfsprogs/btrfsinspect/rebuildmappings/kmp_test.go
index 910452a..acec9b8 100644
--- a/lib/btrfsprogs/btrfsinspect/rebuildmappings/kmp_test.go
+++ b/lib/btrfsprogs/btrfsinspect/rebuildmappings/kmp_test.go
@@ -6,7 +6,6 @@ package rebuildmappings
 
 import (
 	"bytes"
-	"io"
 	"testing"
 
 	"github.com/stretchr/testify/assert"
@@ -15,11 +14,28 @@ import (
 	"git.lukeshu.com/btrfs-progs-ng/lib/diskio"
 )
 
+type bytePattern[K ~int64 | ~int] []byte
+
+var _ kmpPattern[int, byte] = bytePattern[int]{}
+
+// PatLen implements kmpPattern.
+func (s bytePattern[K]) PatLen() K {
+	return K(len(s))
+}
+
+// PatGet implements kmpPattern.
+func (s bytePattern[K]) PatGet(i K) (byte, bool) {
+	chr := s[int(i)]
+	if chr == '.' {
+		return 0, false
+	}
+	return chr, true
+}
+
 func TestBuildKMPTable(t *testing.T) {
 	t.Parallel()
-	substr := diskio.SliceSequence[int64, byte]([]byte("ababaa"))
-	table, err := buildKMPTable[int64, byte](substr)
-	require.NoError(t, err)
+	substr := bytePattern[int64]([]byte("ababaa"))
+	table := buildKMPTable[int64, byte](substr)
 	require.Equal(t,
 		[]int64{0, 0, 1, 2, 3, 1},
 		table)
@@ -33,8 +49,7 @@ func TestBuildKMPTable(t *testing.T) {
 func FuzzBuildKMPTable(f *testing.F) {
 	f.Add([]byte("ababaa"))
 	f.Fuzz(func(t *testing.T, substr []byte) {
-		table, err := buildKMPTable[int64, byte](diskio.SliceSequence[int64, byte](substr))
-		require.NoError(t, err)
+		table := buildKMPTable[int64, byte](bytePattern[int64](substr))
 		require.Equal(t, len(substr), len(table), "length")
 		for j, val := range table {
 			matchLen := j + 1
@@ -62,27 +77,13 @@ func FuzzIndexAll(f *testing.F) {
 		t.Logf("str   =%q", str)
 		t.Logf("substr=%q", substr)
 		exp := NaiveIndexAll(str, substr)
-		act, err := IndexAll[int64, byte](
-			&diskio.ByteReaderSequence[int64]{R: bytes.NewReader(str)},
-			diskio.SliceSequence[int64, byte](substr))
-		assert.NoError(t, err)
+		act := indexAll[int64, byte](
+			diskio.SliceSequence[int64, byte](str),
+			bytePattern[int64](substr))
 		assert.Equal(t, exp, act)
 	})
 }
 
-type RESeq string
-
-func (re RESeq) Get(i int64) (byte, error) {
-	if i < 0 || i >= int64(len(re)) {
-		return 0, io.EOF
-	}
-	chr := re[int(i)]
-	if chr == '.' {
-		return 0, ErrWildcard
-	}
-	return chr, nil
-}
-
 func TestKMPWildcard(t *testing.T) {
 	t.Parallel()
 	type testcase struct {
@@ -116,10 +117,9 @@ func TestKMPWildcard(t *testing.T) {
 		tc := tc
 		t.Run(tcName, func(t *testing.T) {
 			t.Parallel()
-			matches, err := IndexAll[int64, byte](
+			matches := indexAll[int64, byte](
 				diskio.StringSequence[int64](tc.InStr),
-				RESeq(tc.InSubstr))
-			assert.NoError(t, err)
+				bytePattern[int64](tc.InSubstr))
 			assert.Equal(t, tc.ExpMatches, matches)
 		})
 	}
diff --git a/lib/btrfsprogs/btrfsinspect/rebuildmappings/matchsums.go b/lib/btrfsprogs/btrfsinspect/rebuildmappings/matchsums.go
index eda37bd..a3e724e 100644
--- a/lib/btrfsprogs/btrfsinspect/rebuildmappings/matchsums.go
+++ b/lib/btrfsprogs/btrfsinspect/rebuildmappings/matchsums.go
@@ -36,10 +36,7 @@ func matchBlockGroupSums(ctx context.Context,
 
 		var matches []btrfsvol.QualifiedPhysicalAddr
 		if err := WalkUnmappedPhysicalRegions(ctx, physicalSums, regions, func(devID btrfsvol.DeviceID, region btrfssum.SumRun[btrfsvol.PhysicalAddr]) error {
-			rawMatches, err := IndexAll[int64, btrfssum.ShortSum](region, bgRun)
-			if err != nil {
-				return err
-			}
+			rawMatches := indexAll[int, btrfssum.ShortSum](region, bgRun)
 			for _, match := range rawMatches {
 				matches = append(matches, btrfsvol.QualifiedPhysicalAddr{
 					Dev:  devID,
diff --git a/lib/btrfsprogs/btrfsinspect/rebuildmappings/rebuildmappings.go b/lib/btrfsprogs/btrfsinspect/rebuildmappings/rebuildmappings.go
index 665bc96..cdf5e5a 100644
--- a/lib/btrfsprogs/btrfsinspect/rebuildmappings/rebuildmappings.go
+++ b/lib/btrfsprogs/btrfsinspect/rebuildmappings/rebuildmappings.go
@@ -158,10 +158,6 @@ func RebuildMappings(ctx context.Context, fs *btrfs.FS, scanResults btrfsinspect
 	// The fuzzy-search is only fast because the exact-search is so good at getting `physicalBlocks` down.
 	// Empirically: if I remove the exact-search step, then the fuzzy-match step is more than an order of magnitude
 	// slower.
-	//
-	// The exact-search probably could be optimized to be substantially faster (by a constant factor; not affecting
-	// the big-O) by figuring out how to inline function calls and get reduce allocations, but IMO it's "fast
-	// enough" for now.
 	ctx = dlog.WithField(_ctx, "btrfsinspect.rebuild-mappings.step", "5/6")
 	dlog.Infof(_ctx, "5/6: Searching for %d block groups in checksum map (exact)...", len(bgs))
 	physicalSums := ExtractPhysicalSums(scanResults)
diff --git a/lib/btrfsprogs/btrfsinspect/rebuildmappings/sumrunwithgaps.go b/lib/btrfsprogs/btrfsinspect/rebuildmappings/sumrunwithgaps.go
index d1064d8..e574540 100644
--- a/lib/btrfsprogs/btrfsinspect/rebuildmappings/sumrunwithgaps.go
+++ b/lib/btrfsprogs/btrfsinspect/rebuildmappings/sumrunwithgaps.go
@@ -30,15 +30,16 @@ var (
 	_ lowmemjson.Decodable = (*SumRunWithGaps[btrfsvol.LogicalAddr])(nil)
 )
 
-func (sg SumRunWithGaps[Addr]) NumSums() int {
+// PatLen implements kmpPattern[int, ShortSum].
+func (sg SumRunWithGaps[Addr]) PatLen() int {
 	return int(sg.Size / btrfssum.BlockSize)
 }
 
 func (sg SumRunWithGaps[Addr]) PctFull() float64 {
-	total := sg.NumSums()
+	total := sg.PatLen()
 	var full int
 	for _, run := range sg.Runs {
-		full += run.NumSums()
+		full += run.SeqLen()
 	}
 	return float64(full) / float64(total)
 }
@@ -56,21 +57,21 @@ func (sg SumRunWithGaps[Addr]) RunForAddr(addr Addr) (btrfssum.SumRun[Addr], Add
 	return btrfssum.SumRun[Addr]{}, math.MaxInt64, false
 }
 
-func (sg SumRunWithGaps[Addr]) SumForAddr(addr Addr) (btrfssum.ShortSum, error) {
+func (sg SumRunWithGaps[Addr]) SumForAddr(addr Addr) (btrfssum.ShortSum, bool) {
 	if addr < sg.Addr || addr >= sg.Addr.Add(sg.Size) {
-		return "", io.EOF
+		return "", false
 	}
 	for _, run := range sg.Runs {
 		if run.Addr > addr {
-			return "", ErrWildcard
+			return "", false
 		}
 		if run.Addr.Add(run.Size()) <= addr {
 			continue
 		}
 		off := int((addr-run.Addr)/btrfssum.BlockSize) * run.ChecksumSize
-		return run.Sums[off : off+run.ChecksumSize], nil
+		return run.Sums[off : off+run.ChecksumSize], true
 	}
-	return "", ErrWildcard
+	return "", false
 }
 
 func (sg SumRunWithGaps[Addr]) Walk(ctx context.Context, fn func(Addr, btrfssum.ShortSum) error) error {
@@ -82,8 +83,8 @@ func (sg SumRunWithGaps[Addr]) Walk(ctx context.Context, fn func(Addr, btrfssum.
 	return nil
 }
 
-// Get implements diskio.Sequence[int, ShortSum]
-func (sg SumRunWithGaps[Addr]) Get(sumIdx int64) (btrfssum.ShortSum, error) {
+// PatGet implements kmpPattern[int, ShortSum].
+func (sg SumRunWithGaps[Addr]) PatGet(sumIdx int) (btrfssum.ShortSum, bool) {
 	addr := sg.Addr.Add(btrfsvol.AddrDelta(sumIdx) * btrfssum.BlockSize)
 	return sg.SumForAddr(addr)
 }
-- 
cgit v1.2.3-2-g168b


From a55b390d0c14aac4ac4d482ea147bd83841efb46 Mon Sep 17 00:00:00 2001
From: Luke Shumaker <lukeshu@lukeshu.com>
Date: Sat, 4 Feb 2023 02:35:24 -0700
Subject: rebuildmappings: Use a binary-search when looking up the SumForAddr

---
 .../btrfsinspect/rebuildmappings/sumrunwithgaps.go | 24 ++++++++++++++--------
 1 file changed, 15 insertions(+), 9 deletions(-)

(limited to 'lib/btrfsprogs')

diff --git a/lib/btrfsprogs/btrfsinspect/rebuildmappings/sumrunwithgaps.go b/lib/btrfsprogs/btrfsinspect/rebuildmappings/sumrunwithgaps.go
index e574540..f79e2be 100644
--- a/lib/btrfsprogs/btrfsinspect/rebuildmappings/sumrunwithgaps.go
+++ b/lib/btrfsprogs/btrfsinspect/rebuildmappings/sumrunwithgaps.go
@@ -14,6 +14,7 @@ import (
 
 	"git.lukeshu.com/btrfs-progs-ng/lib/btrfs/btrfssum"
 	"git.lukeshu.com/btrfs-progs-ng/lib/btrfs/btrfsvol"
+	"git.lukeshu.com/btrfs-progs-ng/lib/slices"
 )
 
 type SumRunWithGaps[Addr btrfsvol.IntAddr[Addr]] struct {
@@ -61,17 +62,22 @@ func (sg SumRunWithGaps[Addr]) SumForAddr(addr Addr) (btrfssum.ShortSum, bool) {
 	if addr < sg.Addr || addr >= sg.Addr.Add(sg.Size) {
 		return "", false
 	}
-	for _, run := range sg.Runs {
-		if run.Addr > addr {
-			return "", false
-		}
-		if run.Addr.Add(run.Size()) <= addr {
-			continue
+	runIdx, ok := slices.Search(sg.Runs, func(run btrfssum.SumRun[Addr]) int {
+		switch {
+		case addr < run.Addr:
+			return -1
+		case addr >= run.Addr.Add(run.Size()):
+			return 1
+		default:
+			return 0
 		}
-		off := int((addr-run.Addr)/btrfssum.BlockSize) * run.ChecksumSize
-		return run.Sums[off : off+run.ChecksumSize], true
+	})
+	if !ok {
+		return "", false
 	}
-	return "", false
+	run := sg.Runs[runIdx]
+	off := int((addr-run.Addr)/btrfssum.BlockSize) * run.ChecksumSize
+	return run.Sums[off : off+run.ChecksumSize], true
 }
 
 func (sg SumRunWithGaps[Addr]) Walk(ctx context.Context, fn func(Addr, btrfssum.ShortSum) error) error {
-- 
cgit v1.2.3-2-g168b