move chunk reconstruction to btrfsinspect, add --mappings

5 files changed, 315 insertions, 8 deletions

diff --git a/lib/btrfs/btrfsvol/lvm.go b/lib/btrfs/btrfsvol/lvm.go
index c25bd43..65636f6 100644
--- a/lib/btrfs/btrfsvol/lvm.go
+++ b/lib/btrfs/btrfsvol/lvm.go
@@ -99,8 +99,8 @@ type Mapping struct {
 	LAddr      LogicalAddr
 	PAddr      QualifiedPhysicalAddr
 	Size       AddrDelta
-	SizeLocked bool
-	Flags      *BlockGroupFlags
+	SizeLocked bool             `json:",omitempty"`
+	Flags      *BlockGroupFlags `json:",omitempty"`
 }
 
 func (lv *LogicalVolume[PhysicalVolume]) AddMapping(m Mapping) error {
diff --git a/lib/btrfsprogs/btrfsinspect/print_addrspace.go b/lib/btrfsprogs/btrfsinspect/print_addrspace.go
new file mode 100644
index 0000000..d291b7c
--- /dev/null
+++ b/lib/btrfsprogs/btrfsinspect/print_addrspace.go
@@ -0,0 +1,77 @@
+// Copyright (C) 2022  Luke Shumaker <lukeshu@lukeshu.com>
+//
+// SPDX-License-Identifier: GPL-2.0-or-later
+
+package btrfsinspect
+
+import (
+	"fmt"
+	"io"
+	"sort"
+
+	"golang.org/x/text/message"
+
+	"git.lukeshu.com/btrfs-progs-ng/lib/btrfs"
+	"git.lukeshu.com/btrfs-progs-ng/lib/btrfs/btrfsvol"
+)
+
+func PrintLogicalSpace(out io.Writer, fs *btrfs.FS) {
+	mappings := fs.LV.Mappings()
+	var prevBeg, prevEnd btrfsvol.LogicalAddr
+	var sumHole, sumChunk btrfsvol.AddrDelta
+	for _, mapping := range mappings {
+		if mapping.LAddr > prevEnd {
+			size := mapping.LAddr.Sub(prevEnd)
+			fmt.Fprintf(out, "logical_hole laddr=%v size=%v\n", prevEnd, size)
+			sumHole += size
+		}
+		if mapping.LAddr != prevBeg {
+			if mapping.Flags == nil {
+				fmt.Fprintf(out, "chunk laddr=%v size=%v flags=(missing)\n",
+					mapping.LAddr, mapping.Size)
+			} else {
+				fmt.Fprintf(out, "chunk laddr=%v size=%v flags=%v\n",
+					mapping.LAddr, mapping.Size, *mapping.Flags)
+			}
+		}
+		fmt.Fprintf(out, "\tstripe dev_id=%v paddr=%v\n",
+			mapping.PAddr.Dev, mapping.PAddr.Addr)
+		sumChunk += mapping.Size
+		prevBeg = mapping.LAddr
+		prevEnd = mapping.LAddr.Add(mapping.Size)
+	}
+	p := message.NewPrinter(message.MatchLanguage("en"))
+	p.Fprintf(out, "total logical holes      = %v (%d)\n", sumHole, int64(sumHole))
+	p.Fprintf(out, "total logical chunks     = %v (%d)\n", sumChunk, int64(sumChunk))
+	p.Fprintf(out, "total logical addr space = %v (%d)\n", prevEnd, int64(prevEnd))
+}
+
+func PrintPhysicalSpace(out io.Writer, fs *btrfs.FS) {
+	mappings := fs.LV.Mappings()
+	sort.Slice(mappings, func(i, j int) bool {
+		return mappings[i].PAddr.Cmp(mappings[j].PAddr) < 0
+	})
+
+	var prevDev btrfsvol.DeviceID = 0
+	var prevEnd btrfsvol.PhysicalAddr
+	var sumHole, sumExt btrfsvol.AddrDelta
+	for _, mapping := range mappings {
+		if mapping.PAddr.Dev != prevDev {
+			prevDev = mapping.PAddr.Dev
+			prevEnd = 0
+		}
+		if mapping.PAddr.Addr > prevEnd {
+			size := mapping.PAddr.Addr.Sub(prevEnd)
+			fmt.Fprintf(out, "physical_hole paddr=%v size=%v\n", prevEnd, size)
+			sumHole += size
+		}
+		fmt.Fprintf(out, "devext dev=%v paddr=%v size=%v laddr=%v\n",
+			mapping.PAddr.Dev, mapping.PAddr.Addr, mapping.Size, mapping.LAddr)
+		sumExt += mapping.Size
+		prevEnd = mapping.PAddr.Addr.Add(mapping.Size)
+	}
+	p := message.NewPrinter(message.MatchLanguage("en"))
+	p.Fprintf(out, "total physical holes      = %v (%d)\n", sumHole, int64(sumHole))
+	p.Fprintf(out, "total physical extents    = %v (%d)\n", sumExt, int64(sumExt))
+	p.Fprintf(out, "total physical addr space = %v (%d)\n", prevEnd, int64(prevEnd))
+}
diff --git a/lib/btrfsprogs/btrfsinspect/recoverchunks.go b/lib/btrfsprogs/btrfsinspect/recoverchunks.go
new file mode 100644
index 0000000..354328e
--- /dev/null
+++ b/lib/btrfsprogs/btrfsinspect/recoverchunks.go
@@ -0,0 +1,223 @@
+// Copyright (C) 2022  Luke Shumaker <lukeshu@lukeshu.com>
+//
+// SPDX-License-Identifier: GPL-2.0-or-later
+
+package btrfsinspect
+
+import (
+	"context"
+	"sort"
+
+	"github.com/datawire/dlib/dlog"
+
+	"git.lukeshu.com/btrfs-progs-ng/lib/btrfs"
+	"git.lukeshu.com/btrfs-progs-ng/lib/btrfs/btrfsitem"
+	"git.lukeshu.com/btrfs-progs-ng/lib/btrfs/btrfsvol"
+	"git.lukeshu.com/btrfs-progs-ng/lib/btrfsprogs/btrfsutil"
+	"git.lukeshu.com/btrfs-progs-ng/lib/util"
+)
+
+type ScanOneDevResult struct {
+	FoundNodes       map[btrfsvol.LogicalAddr][]btrfsvol.PhysicalAddr
+	FoundChunks      []btrfs.SysChunk
+	FoundBlockGroups []SysBlockGroup
+	FoundDevExtents  []SysDevExtent
+}
+
+type SysBlockGroup struct {
+	Key btrfs.Key
+	BG  btrfsitem.BlockGroup
+}
+
+type SysDevExtent struct {
+	Key    btrfs.Key
+	DevExt btrfsitem.DevExtent
+}
+
+func (found ScanOneDevResult) AddToLV(ctx context.Context, fs *btrfs.FS, dev *btrfs.Device) {
+	sb, _ := dev.Superblock()
+
+	total := len(found.FoundChunks) + len(found.FoundDevExtents)
+	for _, paddrs := range found.FoundNodes {
+		total += len(paddrs)
+	}
+	lastProgress := -1
+	done := 0
+	printProgress := func() {
+		pct := int(100 * float64(done) / float64(total))
+		if pct != lastProgress || done == total {
+			dlog.Infof(ctx, "... dev[%q] added %v%% of the mappings (%v/%v=>%v)",
+				dev.Name(), pct, done, total, len(fs.LV.Mappings()))
+			lastProgress = pct
+		}
+	}
+	printProgress()
+
+	for _, chunk := range found.FoundChunks {
+		for _, mapping := range chunk.Chunk.Mappings(chunk.Key) {
+			if err := fs.LV.AddMapping(mapping); err != nil {
+				dlog.Errorf(ctx, "... dev[%q] error: adding chunk: %v",
+					dev.Name(), err)
+			}
+			done++
+			printProgress()
+		}
+	}
+
+	for _, ext := range found.FoundDevExtents {
+		if err := fs.LV.AddMapping(ext.DevExt.Mapping(ext.Key)); err != nil {
+			dlog.Errorf(ctx, "... dev[%q] error: adding devext: %v",
+				dev.Name(), err)
+		}
+		done++
+		printProgress()
+	}
+
+	// Do the nodes last to avoid bloating the mappings table too
+	// much. (Because nodes are numerous and small, while the
+	// others are few and large; so it is likely that many of the
+	// nodes will be subsumed by other things.)
+	//
+	// Sort them so that progress numbers are predictable.
+	for _, laddr := range util.SortedMapKeys(found.FoundNodes) {
+		for _, paddr := range found.FoundNodes[laddr] {
+			if err := fs.LV.AddMapping(btrfsvol.Mapping{
+				LAddr: laddr,
+				PAddr: btrfsvol.QualifiedPhysicalAddr{
+					Dev:  sb.Data.DevItem.DevID,
+					Addr: paddr,
+				},
+				Size:       btrfsvol.AddrDelta(sb.Data.NodeSize),
+				SizeLocked: false,
+				Flags:      nil,
+			}); err != nil {
+				dlog.Errorf(ctx, "... dev[%q] error: adding node ident: %v",
+					dev.Name(), err)
+			}
+			done++
+			printProgress()
+		}
+	}
+
+	// Use block groups to add missing flags (and as a hint to
+	// combine node entries).
+	//
+	// First dedup them, because they change for allocations and
+	// CoW means that they'll bounce around a lot, so you likely
+	// have oodles of duplicates?
+	type blockgroup struct {
+		LAddr btrfsvol.LogicalAddr
+		Size  btrfsvol.AddrDelta
+		Flags btrfsvol.BlockGroupFlags
+	}
+	bgsSet := make(map[blockgroup]struct{})
+	for _, bg := range found.FoundBlockGroups {
+		bgsSet[blockgroup{
+			LAddr: btrfsvol.LogicalAddr(bg.Key.ObjectID),
+			Size:  btrfsvol.AddrDelta(bg.Key.Offset),
+			Flags: bg.BG.Flags,
+		}] = struct{}{}
+	}
+	bgsOrdered := util.MapKeys(bgsSet)
+	sort.Slice(bgsOrdered, func(i, j int) bool {
+		return bgsOrdered[i].LAddr < bgsOrdered[j].LAddr
+	})
+	for _, bg := range bgsOrdered {
+		otherLAddr, otherPAddr := fs.LV.ResolveAny(bg.LAddr, bg.Size)
+		if otherLAddr < 0 || otherPAddr.Addr < 0 {
+			dlog.Errorf(ctx, "... dev[%q] error: could not pair blockgroup laddr=%v (size=%v flags=%v) with a mapping",
+				dev.Name(), bg.LAddr, bg.Size, bg.Flags)
+			continue
+		}
+
+		offsetWithinChunk := otherLAddr.Sub(bg.LAddr)
+		flags := bg.Flags
+		mapping := btrfsvol.Mapping{
+			LAddr: bg.LAddr,
+			PAddr: btrfsvol.QualifiedPhysicalAddr{
+				Dev:  otherPAddr.Dev,
+				Addr: otherPAddr.Addr.Add(-offsetWithinChunk),
+			},
+			Size:       bg.Size,
+			SizeLocked: true,
+			Flags:      &flags,
+		}
+		if err := fs.LV.AddMapping(mapping); err != nil {
+			dlog.Errorf(ctx, "... dev[%q] error: adding flags from blockgroup: %v",
+				dev.Name(), err)
+		}
+	}
+}
+
+func ScanOneDev(ctx context.Context, dev *btrfs.Device, superblock btrfs.Superblock) (ScanOneDevResult, error) {
+	result := ScanOneDevResult{
+		FoundNodes: make(map[btrfsvol.LogicalAddr][]btrfsvol.PhysicalAddr),
+	}
+
+	devSize, _ := dev.Size()
+	lastProgress := -1
+
+	err := btrfsutil.ScanForNodes(ctx, dev, superblock, func(nodeRef *util.Ref[btrfsvol.PhysicalAddr, btrfs.Node], err error) {
+		if err != nil {
+			dlog.Infof(ctx, "... dev[%q] error: %v", dev.Name(), err)
+			return
+		}
+		result.FoundNodes[nodeRef.Data.Head.Addr] = append(result.FoundNodes[nodeRef.Data.Head.Addr], nodeRef.Addr)
+		for i, item := range nodeRef.Data.BodyLeaf {
+			switch item.Head.Key.ItemType {
+			case btrfsitem.CHUNK_ITEM_KEY:
+				chunk, ok := item.Body.(btrfsitem.Chunk)
+				if !ok {
+					dlog.Errorf(ctx, "... dev[%q] node@%v: item %v: error: type is CHUNK_ITEM_KEY, but struct is %T",
+						dev.Name(), nodeRef.Addr, i, item.Body)
+					continue
+				}
+				//dlog.Tracef(ctx, "... dev[%q] node@%v: item %v: found chunk",
+				//	dev.Name(), nodeRef.Addr, i)
+				result.FoundChunks = append(result.FoundChunks, btrfs.SysChunk{
+					Key:   item.Head.Key,
+					Chunk: chunk,
+				})
+			case btrfsitem.BLOCK_GROUP_ITEM_KEY:
+				bg, ok := item.Body.(btrfsitem.BlockGroup)
+				if !ok {
+					dlog.Errorf(ctx, "... dev[%q] node@%v: item %v: error: type is BLOCK_GROUP_ITEM_KEY, but struct is %T",
+						dev.Name(), nodeRef.Addr, i, item.Body)
+					continue
+				}
+				//dlog.Tracef(ctx, "... dev[%q] node@%v: item %v: found block group",
+				//	dev.Name(), nodeRef.Addr, i)
+				result.FoundBlockGroups = append(result.FoundBlockGroups, SysBlockGroup{
+					Key: item.Head.Key,
+					BG:  bg,
+				})
+			case btrfsitem.DEV_EXTENT_KEY:
+				devext, ok := item.Body.(btrfsitem.DevExtent)
+				if !ok {
+					dlog.Errorf(ctx, "... dev[%q] node@%v: item %v: error: type is DEV_EXTENT_KEY, but struct is %T",
+						dev.Name(), nodeRef.Addr, i, item.Body)
+					continue
+				}
+				//dlog.Tracef(ctx, "... dev[%q] node@%v: item %v: found dev extent",
+				//	dev.Name(), nodeRef.Addr, i)
+				result.FoundDevExtents = append(result.FoundDevExtents, SysDevExtent{
+					Key:    item.Head.Key,
+					DevExt: devext,
+				})
+			}
+		}
+	}, func(pos btrfsvol.PhysicalAddr) {
+		pct := int(100 * float64(pos) / float64(devSize))
+		if pct != lastProgress || pos == devSize {
+			dlog.Infof(ctx, "... dev[%q] scanned %v%% (found: %v nodes, %v chunks, %v block groups, %v dev extents)",
+				dev.Name(), pct,
+				len(result.FoundNodes),
+				len(result.FoundChunks),
+				len(result.FoundBlockGroups),
+				len(result.FoundDevExtents))
+			lastProgress = pct
+		}
+	})
+
+	return result, err
+}
diff --git a/lib/btrfsprogs/btrfsutil/open.go b/lib/btrfsprogs/btrfsutil/open.go
index cc081a6..80bfe7a 100644
--- a/lib/btrfsprogs/btrfsutil/open.go
+++ b/lib/btrfsprogs/btrfsutil/open.go
@@ -5,23 +5,26 @@
 package btrfsutil
 
 import (
+	"context"
 	"fmt"
 	"os"
 
+	"github.com/datawire/dlib/dlog"
+
 	"git.lukeshu.com/btrfs-progs-ng/lib/btrfs"
 )
 
-func Open(flag int, filenames ...string) (*btrfs.FS, error) {
+func Open(ctx context.Context, flag int, filenames ...string) (*btrfs.FS, error) {
 	fs := new(btrfs.FS)
-	for _, filename := range filenames {
+	for i, filename := range filenames {
+		dlog.Debugf(ctx, "Adding device file %d/%d %q...", i, len(filenames), filename)
 		fh, err := os.OpenFile(filename, flag, 0)
 		if err != nil {
 			_ = fs.Close()
-			return nil, fmt.Errorf("file %q: %w", filename, err)
+			return nil, fmt.Errorf("device file %q: %w", filename, err)
 		}
 		if err := fs.AddDevice(&btrfs.Device{File: fh}); err != nil {
-			_ = fs.Close()
-			return nil, fmt.Errorf("file %q: %w", filename, err)
+			dlog.Errorf(ctx, "device file %q: %v", filename, err)
 		}
 	}
 	return fs, nil
diff --git a/lib/btrfsprogs/btrfsutil/scan.go b/lib/btrfsprogs/btrfsutil/scan.go
index d83525c..02d4124 100644
--- a/lib/btrfsprogs/btrfsutil/scan.go
+++ b/lib/btrfsprogs/btrfsutil/scan.go
@@ -5,6 +5,7 @@
 package btrfsutil
 
 import (
+	"context"
 	"errors"
 	"fmt"
 
@@ -17,7 +18,7 @@ import (
 // cmds/rescue-chunk-recover.c:scan_one_device(), except rather than
 // doing something itself when it finds a node, it simply calls a
 // callback function.
-func ScanForNodes(dev *btrfs.Device, sb btrfs.Superblock, fn func(*util.Ref[btrfsvol.PhysicalAddr, btrfs.Node], error), prog func(btrfsvol.PhysicalAddr)) error {
+func ScanForNodes(ctx context.Context, dev *btrfs.Device, sb btrfs.Superblock, fn func(*util.Ref[btrfsvol.PhysicalAddr, btrfs.Node], error), prog func(btrfsvol.PhysicalAddr)) error {
 	devSize, err := dev.Size()
 	if err != nil {
 		return err
@@ -29,6 +30,9 @@ func ScanForNodes(dev *btrfs.Device, sb btrfs.Superblock, fn func(*util.Ref[btrf
 	}
 
 	for pos := btrfsvol.PhysicalAddr(0); pos+btrfsvol.PhysicalAddr(sb.NodeSize) < devSize; pos += btrfsvol.PhysicalAddr(sb.SectorSize) {
+		if ctx.Err() != nil {
+			return ctx.Err()
+		}
 		if util.InSlice(pos, btrfs.SuperblockAddrs) {
 			//fmt.Printf("sector@%v is a superblock\n", pos)
 			continue