summaryrefslogtreecommitdiff
path: root/lib/btrfsprogs
diff options
context:
space:
mode:
Diffstat (limited to 'lib/btrfsprogs')
-rw-r--r--lib/btrfsprogs/btrfsinspect/mount.go482
-rw-r--r--lib/btrfsprogs/btrfsinspect/print_addrspace.go73
-rw-r--r--lib/btrfsprogs/btrfsinspect/print_tree.go443
-rw-r--r--lib/btrfsprogs/btrfsinspect/rebuildmappings/blockgroups.go58
-rw-r--r--lib/btrfsprogs/btrfsinspect/rebuildmappings/fuzzymatchsums.go159
-rw-r--r--lib/btrfsprogs/btrfsinspect/rebuildmappings/kmp.go113
-rw-r--r--lib/btrfsprogs/btrfsinspect/rebuildmappings/kmp_test.go126
-rw-r--r--lib/btrfsprogs/btrfsinspect/rebuildmappings/logicalsums.go249
-rw-r--r--lib/btrfsprogs/btrfsinspect/rebuildmappings/matchsums.go78
-rw-r--r--lib/btrfsprogs/btrfsinspect/rebuildmappings/physicalsums.go89
-rw-r--r--lib/btrfsprogs/btrfsinspect/rebuildmappings/rebuildmappings.go222
-rw-r--r--lib/btrfsprogs/btrfsinspect/rebuildmappings/sumrunwithgaps.go167
-rw-r--r--lib/btrfsprogs/btrfsinspect/rebuildmappings/testdata/fuzz/FuzzIndexAll/593a5dd328ee86bac6820e3f98383aebadd2af3a22aa248546a228b08451c30d3
-rw-r--r--lib/btrfsprogs/btrfsinspect/rebuildmappings/testdata/fuzz/FuzzIndexAll/6bd9babbebf7eb78814e1f3425bfa6ccd6bfd42824a26e8cbd63b5117934e6003
-rw-r--r--lib/btrfsprogs/btrfsinspect/rebuildmappings/testdata/fuzz/FuzzIndexAll/84ed65595ad05a58e293dbf423c1a816b697e2763a29d7c37aa476d6eef6fd603
-rw-r--r--lib/btrfsprogs/btrfsinspect/rebuildmappings/testdata/fuzz/FuzzIndexAll/9be40f71bc49b1b5c3b8e08d58d0f69cc22aefb12fd9b5931e49ff0e419537383
-rw-r--r--lib/btrfsprogs/btrfsinspect/rebuildmappings/testdata/fuzz/FuzzIndexAll/e43317ec61b0da9627d7b2fc0237d369082a6bf5dfe39e05c113b42ff6218d5d3
-rw-r--r--lib/btrfsprogs/btrfsinspect/rebuildnodes/btrees/forrest.go208
-rw-r--r--lib/btrfsprogs/btrfsinspect/rebuildnodes/btrees/nestedlock.go45
-rw-r--r--lib/btrfsprogs/btrfsinspect/rebuildnodes/btrees/tree.go357
-rw-r--r--lib/btrfsprogs/btrfsinspect/rebuildnodes/graph/graph.go265
-rw-r--r--lib/btrfsprogs/btrfsinspect/rebuildnodes/graph/loops.go133
-rw-r--r--lib/btrfsprogs/btrfsinspect/rebuildnodes/keyio/keyio.go172
-rw-r--r--lib/btrfsprogs/btrfsinspect/rebuildnodes/rebuild.go583
-rw-r--r--lib/btrfsprogs/btrfsinspect/rebuildnodes/rebuild_graph.go367
-rw-r--r--lib/btrfsprogs/btrfsinspect/rebuildnodes/rebuild_treecb.go86
-rw-r--r--lib/btrfsprogs/btrfsinspect/rebuildnodes/rebuild_wantcb.go400
-rw-r--r--lib/btrfsprogs/btrfsinspect/rebuildnodes/rebuild_wanttyp.go107
-rw-r--r--lib/btrfsprogs/btrfsinspect/rebuildnodes/scan.go77
-rw-r--r--lib/btrfsprogs/btrfsinspect/rebuildnodes/util.go31
-rw-r--r--lib/btrfsprogs/btrfsinspect/scandevices.go260
-rw-r--r--lib/btrfsprogs/btrfsutil/broken_btree.go363
-rw-r--r--lib/btrfsprogs/btrfsutil/open.go46
-rw-r--r--lib/btrfsprogs/btrfsutil/skinny_paths.go146
-rw-r--r--lib/btrfsprogs/btrfsutil/walk.go97
35 files changed, 0 insertions, 6017 deletions
diff --git a/lib/btrfsprogs/btrfsinspect/mount.go b/lib/btrfsprogs/btrfsinspect/mount.go
deleted file mode 100644
index 0ac8497..0000000
--- a/lib/btrfsprogs/btrfsinspect/mount.go
+++ /dev/null
@@ -1,482 +0,0 @@
-// Copyright (C) 2022-2023 Luke Shumaker <lukeshu@lukeshu.com>
-//
-// SPDX-License-Identifier: GPL-2.0-or-later
-
-package btrfsinspect
-
-import (
- "context"
- "errors"
- "fmt"
- "io"
- "path/filepath"
- "sync"
- "sync/atomic"
- "syscall"
-
- "git.lukeshu.com/go/typedsync"
- "github.com/datawire/dlib/dcontext"
- "github.com/datawire/dlib/dgroup"
- "github.com/datawire/dlib/dlog"
- "github.com/jacobsa/fuse"
- "github.com/jacobsa/fuse/fuseops"
- "github.com/jacobsa/fuse/fuseutil"
-
- "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/btrfsprim"
- "git.lukeshu.com/btrfs-progs-ng/lib/btrfsprogs/btrfsutil"
- "git.lukeshu.com/btrfs-progs-ng/lib/containers"
- "git.lukeshu.com/btrfs-progs-ng/lib/maps"
- "git.lukeshu.com/btrfs-progs-ng/lib/slices"
-)
-
-func MountRO(ctx context.Context, fs *btrfs.FS, mountpoint string, noChecksums bool) error {
- pvs := fs.LV.PhysicalVolumes()
- if len(pvs) < 1 {
- return errors.New("no devices")
- }
-
- deviceName := pvs[maps.SortedKeys(pvs)[0]].Name()
- if abs, err := filepath.Abs(deviceName); err == nil {
- deviceName = abs
- }
-
- rootSubvol := &subvolume{
- Subvolume: btrfs.Subvolume{
- FS: btrfsutil.NewBrokenTrees(ctx, fs),
- TreeID: btrfsprim.FS_TREE_OBJECTID,
- NoChecksums: noChecksums,
- },
- DeviceName: deviceName,
- Mountpoint: mountpoint,
- }
- return rootSubvol.Run(ctx)
-}
-
-func fuseMount(ctx context.Context, mountpoint string, server fuse.Server, cfg *fuse.MountConfig) error {
- grp := dgroup.NewGroup(ctx, dgroup.GroupConfig{
- // Allow mountHandle.Join() returning to cause the
- // "unmount" goroutine to quit.
- ShutdownOnNonError: true,
- })
- mounted := uint32(1)
- grp.Go("unmount", func(ctx context.Context) error {
- <-ctx.Done()
- var err error
- var gotNil bool
- // Keep retrying, because the FS might be busy.
- for atomic.LoadUint32(&mounted) != 0 {
- if _err := fuse.Unmount(mountpoint); _err == nil {
- gotNil = true
- } else if !gotNil {
- err = _err
- }
- }
- if gotNil {
- return nil
- }
- return err
- })
- grp.Go("mount", func(ctx context.Context) error {
- defer atomic.StoreUint32(&mounted, 0)
-
- cfg.OpContext = ctx
- cfg.ErrorLogger = dlog.StdLogger(ctx, dlog.LogLevelError)
- cfg.DebugLogger = dlog.StdLogger(ctx, dlog.LogLevelDebug)
-
- mountHandle, err := fuse.Mount(mountpoint, server, cfg)
- if err != nil {
- return err
- }
- dlog.Infof(ctx, "mounted %q", mountpoint)
- return mountHandle.Join(dcontext.HardContext(ctx))
- })
- return grp.Wait()
-}
-
-type dirState struct {
- Dir *btrfs.Dir
-}
-
-type fileState struct {
- File *btrfs.File
-}
-
-type subvolume struct {
- btrfs.Subvolume
- DeviceName string
- Mountpoint string
-
- fuseutil.NotImplementedFileSystem
- lastHandle uint64
- dirHandles typedsync.Map[fuseops.HandleID, *dirState]
- fileHandles typedsync.Map[fuseops.HandleID, *fileState]
-
- subvolMu sync.Mutex
- subvols containers.Set[string]
- grp *dgroup.Group
-}
-
-func (sv *subvolume) Run(ctx context.Context) error {
- sv.grp = dgroup.NewGroup(ctx, dgroup.GroupConfig{})
- sv.grp.Go("self", func(ctx context.Context) error {
- cfg := &fuse.MountConfig{
- FSName: sv.DeviceName,
- Subtype: "btrfs",
-
- ReadOnly: true,
-
- Options: map[string]string{
- "allow_other": "",
- },
- }
- return fuseMount(ctx, sv.Mountpoint, fuseutil.NewFileSystemServer(sv), cfg)
- })
- return sv.grp.Wait()
-}
-
-func (sv *subvolume) newHandle() fuseops.HandleID {
- return fuseops.HandleID(atomic.AddUint64(&sv.lastHandle, 1))
-}
-
-func inodeItemToFUSE(itemBody btrfsitem.Inode) fuseops.InodeAttributes {
- return fuseops.InodeAttributes{
- Size: uint64(itemBody.Size),
- Nlink: uint32(itemBody.NLink),
- Mode: uint32(itemBody.Mode),
- // RDev: itemBody.Rdev, // jacobsa/fuse doesn't expose rdev
- Atime: itemBody.ATime.ToStd(),
- Mtime: itemBody.MTime.ToStd(),
- Ctime: itemBody.CTime.ToStd(),
- // Crtime: itemBody.OTime,
- Uid: uint32(itemBody.UID),
- Gid: uint32(itemBody.GID),
- }
-}
-
-func (sv *subvolume) LoadDir(inode btrfsprim.ObjID) (val *btrfs.Dir, err error) {
- val, err = sv.Subvolume.LoadDir(inode)
- if val != nil {
- haveSubvolumes := false
- for _, index := range maps.SortedKeys(val.ChildrenByIndex) {
- entry := val.ChildrenByIndex[index]
- if entry.Location.ItemType == btrfsitem.ROOT_ITEM_KEY {
- haveSubvolumes = true
- break
- }
- }
- if haveSubvolumes {
- abspath, _err := val.AbsPath()
- if _err != nil {
- return val, err
- }
- sv.subvolMu.Lock()
- for _, index := range maps.SortedKeys(val.ChildrenByIndex) {
- entry := val.ChildrenByIndex[index]
- if entry.Location.ItemType != btrfsitem.ROOT_ITEM_KEY {
- continue
- }
- if sv.subvols == nil {
- sv.subvols = make(containers.Set[string])
- }
- subMountpoint := filepath.Join(abspath, string(entry.Name))
- if !sv.subvols.Has(subMountpoint) {
- sv.subvols.Insert(subMountpoint)
- workerName := fmt.Sprintf("%d-%s", val.Inode, filepath.Base(subMountpoint))
- sv.grp.Go(workerName, func(ctx context.Context) error {
- subSv := &subvolume{
- Subvolume: btrfs.Subvolume{
- FS: sv.FS,
- TreeID: entry.Location.ObjectID,
- NoChecksums: sv.NoChecksums,
- },
- DeviceName: sv.DeviceName,
- Mountpoint: filepath.Join(sv.Mountpoint, subMountpoint[1:]),
- }
- return subSv.Run(ctx)
- })
- }
- }
- sv.subvolMu.Unlock()
- }
- }
- return val, err
-}
-
-func (sv *subvolume) StatFS(_ context.Context, op *fuseops.StatFSOp) error {
- // See linux.git/fs/btrfs/super.c:btrfs_statfs()
- sb, err := sv.FS.Superblock()
- if err != nil {
- return err
- }
-
- op.IoSize = sb.SectorSize
- op.BlockSize = sb.SectorSize
- op.Blocks = sb.TotalBytes / uint64(sb.SectorSize) // TODO: adjust for RAID type
- // op.BlocksFree = TODO
-
- // btrfs doesn't have a fixed number of inodes
- op.Inodes = 0
- op.InodesFree = 0
-
- // jacobsa/fuse doesn't expose namelen, instead hard-coding it
- // to 255. Which is fine by us, because that's what it is for
- // btrfs.
-
- return nil
-}
-
-func (sv *subvolume) LookUpInode(_ context.Context, op *fuseops.LookUpInodeOp) error {
- if op.Parent == fuseops.RootInodeID {
- parent, err := sv.GetRootInode()
- if err != nil {
- return err
- }
- op.Parent = fuseops.InodeID(parent)
- }
-
- dir, err := sv.LoadDir(btrfsprim.ObjID(op.Parent))
- if err != nil {
- return err
- }
- entry, ok := dir.ChildrenByName[op.Name]
- if !ok {
- return syscall.ENOENT
- }
- if entry.Location.ItemType != btrfsitem.INODE_ITEM_KEY {
- // Subvolume
- //
- // Because each subvolume has its own pool of inodes
- // (as in 2 different subvolumes can have files with
- // te same inode number), so to represent that to FUSE
- // we need to have this be a full separate mountpoint.
- //
- // I'd want to return EIO or EINTR or something here,
- // but both the FUSE userspace tools and the kernel
- // itself stat the mountpoint before mounting it, so
- // we've got to return something bogus here to let
- // that mount happen.
- op.Entry = fuseops.ChildInodeEntry{
- Child: 2, // an inode number that a real file will never have
- Attributes: fuseops.InodeAttributes{
- Nlink: 1,
- Mode: uint32(btrfsitem.ModeFmtDir | 0o700), //nolint:gomnd // TODO
- },
- }
- return nil
- }
- bareInode, err := sv.LoadBareInode(entry.Location.ObjectID)
- if err != nil {
- return err
- }
- op.Entry = fuseops.ChildInodeEntry{
- Child: fuseops.InodeID(entry.Location.ObjectID),
- Generation: fuseops.GenerationNumber(bareInode.InodeItem.Sequence),
- Attributes: inodeItemToFUSE(*bareInode.InodeItem),
- }
- return nil
-}
-
-func (sv *subvolume) GetInodeAttributes(_ context.Context, op *fuseops.GetInodeAttributesOp) error {
- if op.Inode == fuseops.RootInodeID {
- inode, err := sv.GetRootInode()
- if err != nil {
- return err
- }
- op.Inode = fuseops.InodeID(inode)
- }
-
- bareInode, err := sv.LoadBareInode(btrfsprim.ObjID(op.Inode))
- if err != nil {
- return err
- }
-
- op.Attributes = inodeItemToFUSE(*bareInode.InodeItem)
- return nil
-}
-
-func (sv *subvolume) OpenDir(_ context.Context, op *fuseops.OpenDirOp) error {
- if op.Inode == fuseops.RootInodeID {
- inode, err := sv.GetRootInode()
- if err != nil {
- return err
- }
- op.Inode = fuseops.InodeID(inode)
- }
-
- dir, err := sv.LoadDir(btrfsprim.ObjID(op.Inode))
- if err != nil {
- return err
- }
- handle := sv.newHandle()
- sv.dirHandles.Store(handle, &dirState{
- Dir: dir,
- })
- op.Handle = handle
- return nil
-}
-
-func (sv *subvolume) ReadDir(_ context.Context, op *fuseops.ReadDirOp) error {
- state, ok := sv.dirHandles.Load(op.Handle)
- if !ok {
- return syscall.EBADF
- }
- origOffset := op.Offset
- for _, index := range maps.SortedKeys(state.Dir.ChildrenByIndex) {
- if index < uint64(origOffset) {
- continue
- }
- entry := state.Dir.ChildrenByIndex[index]
- n := fuseutil.WriteDirent(op.Dst[op.BytesRead:], fuseutil.Dirent{
- Offset: fuseops.DirOffset(index + 1),
- Inode: fuseops.InodeID(entry.Location.ObjectID),
- Name: string(entry.Name),
- Type: map[btrfsitem.FileType]fuseutil.DirentType{
- btrfsitem.FT_UNKNOWN: fuseutil.DT_Unknown,
- btrfsitem.FT_REG_FILE: fuseutil.DT_File,
- btrfsitem.FT_DIR: fuseutil.DT_Directory,
- btrfsitem.FT_CHRDEV: fuseutil.DT_Char,
- btrfsitem.FT_BLKDEV: fuseutil.DT_Block,
- btrfsitem.FT_FIFO: fuseutil.DT_FIFO,
- btrfsitem.FT_SOCK: fuseutil.DT_Socket,
- btrfsitem.FT_SYMLINK: fuseutil.DT_Link,
- }[entry.Type],
- })
- if n == 0 {
- break
- }
- op.BytesRead += n
- }
- return nil
-}
-
-func (sv *subvolume) ReleaseDirHandle(_ context.Context, op *fuseops.ReleaseDirHandleOp) error {
- _, ok := sv.dirHandles.LoadAndDelete(op.Handle)
- if !ok {
- return syscall.EBADF
- }
- return nil
-}
-
-func (sv *subvolume) OpenFile(_ context.Context, op *fuseops.OpenFileOp) error {
- file, err := sv.LoadFile(btrfsprim.ObjID(op.Inode))
- if err != nil {
- return err
- }
- handle := sv.newHandle()
- sv.fileHandles.Store(handle, &fileState{
- File: file,
- })
- op.Handle = handle
- op.KeepPageCache = true
- return nil
-}
-
-func (sv *subvolume) ReadFile(_ context.Context, op *fuseops.ReadFileOp) error {
- state, ok := sv.fileHandles.Load(op.Handle)
- if !ok {
- return syscall.EBADF
- }
-
- var dat []byte
- if op.Dst != nil {
- size := slices.Min(int64(len(op.Dst)), op.Size)
- dat = op.Dst[:size]
- } else {
- dat = make([]byte, op.Size)
- op.Data = [][]byte{dat}
- }
-
- var err error
- op.BytesRead, err = state.File.ReadAt(dat, op.Offset)
- if errors.Is(err, io.EOF) {
- err = nil
- }
-
- return err
-}
-
-func (sv *subvolume) ReleaseFileHandle(_ context.Context, op *fuseops.ReleaseFileHandleOp) error {
- _, ok := sv.fileHandles.LoadAndDelete(op.Handle)
- if !ok {
- return syscall.EBADF
- }
- return nil
-}
-
-func (sv *subvolume) ReadSymlink(_ context.Context, op *fuseops.ReadSymlinkOp) error {
- file, err := sv.LoadFile(btrfsprim.ObjID(op.Inode))
- if err != nil {
- return err
- }
- reader := io.NewSectionReader(file, 0, file.InodeItem.Size)
- tgt, err := io.ReadAll(reader)
- if err != nil {
- return err
- }
- op.Target = string(tgt)
- return nil
-}
-
-func (sv *subvolume) ListXattr(_ context.Context, op *fuseops.ListXattrOp) error {
- if op.Inode == fuseops.RootInodeID {
- inode, err := sv.GetRootInode()
- if err != nil {
- return err
- }
- op.Inode = fuseops.InodeID(inode)
- }
-
- fullInode, err := sv.LoadFullInode(btrfsprim.ObjID(op.Inode))
- if err != nil {
- return err
- }
-
- size := 0
- for name := range fullInode.XAttrs {
- size += len(name) + 1
- }
- if len(op.Dst) < size {
- return syscall.ERANGE
- }
-
- op.BytesRead = size
- n := 0
- for _, name := range maps.SortedKeys(fullInode.XAttrs) {
- n += copy(op.Dst[n:], name)
- op.Dst[n] = 0
- n++
- }
- return nil
-}
-
-func (sv *subvolume) GetXattr(_ context.Context, op *fuseops.GetXattrOp) error {
- if op.Inode == fuseops.RootInodeID {
- inode, err := sv.GetRootInode()
- if err != nil {
- return err
- }
- op.Inode = fuseops.InodeID(inode)
- }
-
- fullInode, err := sv.LoadFullInode(btrfsprim.ObjID(op.Inode))
- if err != nil {
- return err
- }
-
- val, ok := fullInode.XAttrs[op.Name]
- if !ok {
- return syscall.ENODATA
- }
-
- if len(op.Dst) < len(val) {
- return syscall.ERANGE
- }
-
- op.BytesRead = len(val)
- copy(op.Dst, val)
- return nil
-}
-
-func (sv *subvolume) Destroy() {}
diff --git a/lib/btrfsprogs/btrfsinspect/print_addrspace.go b/lib/btrfsprogs/btrfsinspect/print_addrspace.go
deleted file mode 100644
index e85e055..0000000
--- a/lib/btrfsprogs/btrfsinspect/print_addrspace.go
+++ /dev/null
@@ -1,73 +0,0 @@
-// Copyright (C) 2022-2023 Luke Shumaker <lukeshu@lukeshu.com>
-//
-// SPDX-License-Identifier: GPL-2.0-or-later
-
-package btrfsinspect
-
-import (
- "io"
- "sort"
-
- "git.lukeshu.com/btrfs-progs-ng/lib/btrfs"
- "git.lukeshu.com/btrfs-progs-ng/lib/btrfs/btrfsvol"
- "git.lukeshu.com/btrfs-progs-ng/lib/textui"
-)
-
-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)
- textui.Fprintf(out, "logical_hole laddr=%v size=%v\n", prevEnd, size)
- sumHole += size
- }
- if mapping.LAddr != prevBeg {
- if !mapping.Flags.OK {
- textui.Fprintf(out, "chunk laddr=%v size=%v flags=(missing)\n",
- mapping.LAddr, mapping.Size)
- } else {
- textui.Fprintf(out, "chunk laddr=%v size=%v flags=%v\n",
- mapping.LAddr, mapping.Size, mapping.Flags.Val)
- }
- }
- textui.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)
- }
- textui.Fprintf(out, "total logical holes = %v (%d)\n", sumHole, int64(sumHole))
- textui.Fprintf(out, "total logical chunks = %v (%d)\n", sumChunk, int64(sumChunk))
- textui.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.Compare(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)
- textui.Fprintf(out, "physical_hole paddr=%v size=%v\n", prevEnd, size)
- sumHole += size
- }
- textui.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)
- }
- textui.Fprintf(out, "total physical holes = %v (%d)\n", sumHole, int64(sumHole))
- textui.Fprintf(out, "total physical extents = %v (%d)\n", sumExt, int64(sumExt))
- textui.Fprintf(out, "total physical addr space = %v (%d)\n", prevEnd, int64(prevEnd))
-}
diff --git a/lib/btrfsprogs/btrfsinspect/print_tree.go b/lib/btrfsprogs/btrfsinspect/print_tree.go
deleted file mode 100644
index 240c72f..0000000
--- a/lib/btrfsprogs/btrfsinspect/print_tree.go
+++ /dev/null
@@ -1,443 +0,0 @@
-// Copyright (C) 2022-2023 Luke Shumaker <lukeshu@lukeshu.com>
-//
-// SPDX-License-Identifier: GPL-2.0-or-later
-
-package btrfsinspect
-
-import (
- "context"
- "io"
-
- "github.com/datawire/dlib/dlog"
-
- "git.lukeshu.com/btrfs-progs-ng/lib/binstruct"
- "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/btrfsprim"
- "git.lukeshu.com/btrfs-progs-ng/lib/btrfs/btrfssum"
- "git.lukeshu.com/btrfs-progs-ng/lib/btrfs/btrfstree"
- "git.lukeshu.com/btrfs-progs-ng/lib/btrfs/btrfsvol"
- "git.lukeshu.com/btrfs-progs-ng/lib/diskio"
- "git.lukeshu.com/btrfs-progs-ng/lib/slices"
- "git.lukeshu.com/btrfs-progs-ng/lib/textui"
-)
-
-func DumpTrees(ctx context.Context, out io.Writer, fs *btrfs.FS) {
- superblock, err := fs.Superblock()
- if err != nil {
- dlog.Error(ctx, err)
- return
- }
-
- if superblock.RootTree != 0 {
- textui.Fprintf(out, "root tree\n")
- printTree(ctx, out, fs, btrfsprim.ROOT_TREE_OBJECTID)
- }
- if superblock.ChunkTree != 0 {
- textui.Fprintf(out, "chunk tree\n")
- printTree(ctx, out, fs, btrfsprim.CHUNK_TREE_OBJECTID)
- }
- if superblock.LogTree != 0 {
- textui.Fprintf(out, "log root tree\n")
- printTree(ctx, out, fs, btrfsprim.TREE_LOG_OBJECTID)
- }
- if superblock.BlockGroupRoot != 0 {
- textui.Fprintf(out, "block group tree\n")
- printTree(ctx, out, fs, btrfsprim.BLOCK_GROUP_TREE_OBJECTID)
- }
- fs.TreeWalk(
- ctx,
- btrfsprim.ROOT_TREE_OBJECTID,
- func(err *btrfstree.TreeError) {
- dlog.Error(ctx, err)
- },
- btrfstree.TreeWalkHandler{
- Item: func(_ btrfstree.TreePath, item btrfstree.Item) error {
- if item.Key.ItemType != btrfsitem.ROOT_ITEM_KEY {
- return nil
- }
- treeName, ok := map[btrfsprim.ObjID]string{
- btrfsprim.ROOT_TREE_OBJECTID: "root",
- btrfsprim.EXTENT_TREE_OBJECTID: "extent",
- btrfsprim.CHUNK_TREE_OBJECTID: "chunk",
- btrfsprim.DEV_TREE_OBJECTID: "device",
- btrfsprim.FS_TREE_OBJECTID: "fs",
- btrfsprim.ROOT_TREE_DIR_OBJECTID: "directory",
- btrfsprim.CSUM_TREE_OBJECTID: "checksum",
- btrfsprim.ORPHAN_OBJECTID: "orphan",
- btrfsprim.TREE_LOG_OBJECTID: "log",
- btrfsprim.TREE_LOG_FIXUP_OBJECTID: "log fixup",
- btrfsprim.TREE_RELOC_OBJECTID: "reloc",
- btrfsprim.DATA_RELOC_TREE_OBJECTID: "data reloc",
- btrfsprim.EXTENT_CSUM_OBJECTID: "extent checksum",
- btrfsprim.QUOTA_TREE_OBJECTID: "quota",
- btrfsprim.UUID_TREE_OBJECTID: "uuid",
- btrfsprim.FREE_SPACE_TREE_OBJECTID: "free space",
- btrfsprim.MULTIPLE_OBJECTIDS: "multiple",
- btrfsprim.BLOCK_GROUP_TREE_OBJECTID: "block group",
- }[item.Key.ObjectID]
- if !ok {
- treeName = "file"
- }
- textui.Fprintf(out, "%v tree key %v \n", treeName, item.Key.Format(btrfsprim.ROOT_TREE_OBJECTID))
- printTree(ctx, out, fs, item.Key.ObjectID)
- return nil
- },
- },
- )
- textui.Fprintf(out, "total bytes %v\n", superblock.TotalBytes)
- textui.Fprintf(out, "bytes used %v\n", superblock.BytesUsed)
- textui.Fprintf(out, "uuid %v\n", superblock.FSUUID)
-}
-
-var nodeHeaderSize = binstruct.StaticSize(btrfstree.NodeHeader{})
-
-// printTree mimics btrfs-progs
-// kernel-shared/print-tree.c:btrfs_print_tree() and
-// kernel-shared/print-tree.c:btrfs_print_leaf()
-func printTree(ctx context.Context, out io.Writer, fs *btrfs.FS, treeID btrfsprim.ObjID) {
- var itemOffset uint32
- handlers := btrfstree.TreeWalkHandler{
- Node: func(path btrfstree.TreePath, nodeRef *diskio.Ref[btrfsvol.LogicalAddr, btrfstree.Node]) error {
- printHeaderInfo(out, nodeRef.Data)
- itemOffset = nodeRef.Data.Size - uint32(nodeHeaderSize)
- return nil
- },
- PreKeyPointer: func(path btrfstree.TreePath, item btrfstree.KeyPointer) error {
- treeID := path[0].FromTree
- textui.Fprintf(out, "\tkey %v block %v gen %v\n",
- item.Key.Format(treeID),
- item.BlockPtr,
- item.Generation)
- return nil
- },
- Item: func(path btrfstree.TreePath, item btrfstree.Item) error {
- treeID := path[0].FromTree
- i := path.Node(-1).FromItemIdx
- bs, _ := binstruct.Marshal(item.Body)
- itemSize := uint32(len(bs))
- itemOffset -= itemSize
- textui.Fprintf(out, "\titem %v key %v itemoff %v itemsize %v\n",
- i,
- item.Key.Format(treeID),
- itemOffset,
- itemSize)
- switch body := item.Body.(type) {
- case *btrfsitem.FreeSpaceHeader:
- textui.Fprintf(out, "\t\tlocation key %v\n", body.Location.Format(treeID))
- textui.Fprintf(out, "\t\tcache generation %v entries %v bitmaps %v\n",
- body.Generation, body.NumEntries, body.NumBitmaps)
- case *btrfsitem.Inode:
- textui.Fprintf(out, ""+
- "\t\tgeneration %v transid %v size %v nbytes %v\n"+
- "\t\tblock group %v mode %o links %v uid %v gid %v rdev %v\n"+
- "\t\tsequence %v flags %v\n",
- body.Generation, body.TransID, body.Size, body.NumBytes,
- body.BlockGroup, body.Mode, body.NLink, body.UID, body.GID, body.RDev,
- body.Sequence, body.Flags)
- textui.Fprintf(out, "\t\tatime %v\n", fmtTime(body.ATime))
- textui.Fprintf(out, "\t\tctime %v\n", fmtTime(body.CTime))
- textui.Fprintf(out, "\t\tmtime %v\n", fmtTime(body.MTime))
- textui.Fprintf(out, "\t\totime %v\n", fmtTime(body.OTime))
- case *btrfsitem.InodeRefs:
- for _, ref := range body.Refs {
- textui.Fprintf(out, "\t\tindex %v namelen %v name: %s\n",
- ref.Index, ref.NameLen, ref.Name)
- }
- // case btrfsitem.INODE_EXTREF_KEY:
- // // TODO
- case *btrfsitem.DirEntry:
- textui.Fprintf(out, "\t\tlocation key %v type %v\n",
- body.Location.Format(treeID), body.Type)
- textui.Fprintf(out, "\t\ttransid %v data_len %v name_len %v\n",
- body.TransID, body.DataLen, body.NameLen)
- textui.Fprintf(out, "\t\tname: %s\n", body.Name)
- if len(body.Data) > 0 {
- textui.Fprintf(out, "\t\tdata %s\n", body.Data)
- }
- // case btrfsitem.DIR_LOG_INDEX_KEY, btrfsitem.DIR_LOG_ITEM_KEY:
- // // TODO
- case *btrfsitem.Root:
- textui.Fprintf(out, "\t\tgeneration %v root_dirid %v bytenr %d byte_limit %v bytes_used %v\n",
- body.Generation, body.RootDirID, body.ByteNr, body.ByteLimit, body.BytesUsed)
- textui.Fprintf(out, "\t\tlast_snapshot %v flags %v refs %v\n",
- body.LastSnapshot, body.Flags, body.Refs)
- textui.Fprintf(out, "\t\tdrop_progress key %v drop_level %v\n",
- body.DropProgress.Format(treeID), body.DropLevel)
- textui.Fprintf(out, "\t\tlevel %v generation_v2 %v\n",
- body.Level, body.GenerationV2)
- if body.Generation == body.GenerationV2 {
- textui.Fprintf(out, "\t\tuuid %v\n", body.UUID)
- textui.Fprintf(out, "\t\tparent_uuid %v\n", body.ParentUUID)
- textui.Fprintf(out, "\t\treceived_uuid %v\n", body.ReceivedUUID)
- textui.Fprintf(out, "\t\tctransid %v otransid %v stransid %v rtransid %v\n",
- body.CTransID, body.OTransID, body.STransID, body.RTransID)
- textui.Fprintf(out, "\t\tctime %v\n", fmtTime(body.CTime))
- textui.Fprintf(out, "\t\totime %v\n", fmtTime(body.OTime))
- textui.Fprintf(out, "\t\tstime %v\n", fmtTime(body.STime))
- textui.Fprintf(out, "\t\trtime %v\n", fmtTime(body.RTime))
- }
- case *btrfsitem.RootRef:
- var tag string
- switch item.Key.ItemType {
- case btrfsitem.ROOT_REF_KEY:
- tag = "ref"
- case btrfsitem.ROOT_BACKREF_KEY:
- tag = "backref"
- default:
- tag = textui.Sprintf("(error: unhandled RootRef item type: %v)", item.Key.ItemType)
- }
- textui.Fprintf(out, "\t\troot %v key dirid %v sequence %v name %s\n",
- tag, body.DirID, body.Sequence, body.Name)
- case *btrfsitem.Extent:
- textui.Fprintf(out, "\t\trefs %v gen %v flags %v\n",
- body.Head.Refs, body.Head.Generation, body.Head.Flags)
- if body.Head.Flags.Has(btrfsitem.EXTENT_FLAG_TREE_BLOCK) {
- textui.Fprintf(out, "\t\ttree block key %v level %v\n",
- body.Info.Key.Format(treeID), body.Info.Level)
- }
- printExtentInlineRefs(out, body.Refs)
- case *btrfsitem.Metadata:
- textui.Fprintf(out, "\t\trefs %v gen %v flags %v\n",
- body.Head.Refs, body.Head.Generation, body.Head.Flags)
- textui.Fprintf(out, "\t\ttree block skinny level %v\n", item.Key.Offset)
- printExtentInlineRefs(out, body.Refs)
- // case btrfsitem.EXTENT_DATA_REF_KEY:
- // // TODO
- // case btrfsitem.SHARED_DATA_REF_KEY:
- // // TODO
- case *btrfsitem.ExtentCSum:
- start := btrfsvol.LogicalAddr(item.Key.Offset)
- textui.Fprintf(out, "\t\trange start %d end %d length %d",
- start, start.Add(body.Size()), body.Size())
- sumsPerLine := slices.Max(1, len(btrfssum.CSum{})/body.ChecksumSize/2)
-
- i := 0
- _ = body.Walk(ctx, func(pos btrfsvol.LogicalAddr, sum btrfssum.ShortSum) error {
- if i%sumsPerLine == 0 {
- textui.Fprintf(out, "\n\t\t")
- } else {
- textui.Fprintf(out, " ")
- }
- textui.Fprintf(out, "[%d] 0x%x", pos, sum)
- i++
- return nil
- })
- textui.Fprintf(out, "\n")
- case *btrfsitem.FileExtent:
- textui.Fprintf(out, "\t\tgeneration %v type %v\n",
- body.Generation, body.Type)
- switch body.Type {
- case btrfsitem.FILE_EXTENT_INLINE:
- textui.Fprintf(out, "\t\tinline extent data size %v ram_bytes %v compression %v\n",
- len(body.BodyInline), body.RAMBytes, body.Compression)
- case btrfsitem.FILE_EXTENT_PREALLOC:
- textui.Fprintf(out, "\t\tprealloc data disk byte %v nr %v\n",
- body.BodyExtent.DiskByteNr,
- body.BodyExtent.DiskNumBytes)
- textui.Fprintf(out, "\t\tprealloc data offset %v nr %v\n",
- body.BodyExtent.Offset,
- body.BodyExtent.NumBytes)
- case btrfsitem.FILE_EXTENT_REG:
- textui.Fprintf(out, "\t\textent data disk byte %d nr %d\n",
- body.BodyExtent.DiskByteNr,
- body.BodyExtent.DiskNumBytes)
- textui.Fprintf(out, "\t\textent data offset %d nr %d ram %v\n",
- body.BodyExtent.Offset,
- body.BodyExtent.NumBytes,
- body.RAMBytes)
- textui.Fprintf(out, "\t\textent compression %v\n",
- body.Compression)
- default:
- textui.Fprintf(out, "\t\t(error) unknown file extent type %v", body.Type)
- }
- case *btrfsitem.BlockGroup:
- textui.Fprintf(out, "\t\tblock group used %v chunk_objectid %v flags %v\n",
- body.Used, body.ChunkObjectID, body.Flags)
- case *btrfsitem.FreeSpaceInfo:
- textui.Fprintf(out, "\t\tfree space info extent count %v flags %d\n",
- body.ExtentCount, body.Flags)
- case *btrfsitem.FreeSpaceBitmap:
- textui.Fprintf(out, "\t\tfree space bitmap\n")
- case *btrfsitem.Chunk:
- textui.Fprintf(out, "\t\tlength %d owner %d stripe_len %v type %v\n",
- body.Head.Size, body.Head.Owner, body.Head.StripeLen, body.Head.Type)
- textui.Fprintf(out, "\t\tio_align %v io_width %v sector_size %v\n",
- body.Head.IOOptimalAlign, body.Head.IOOptimalWidth, body.Head.IOMinSize)
- textui.Fprintf(out, "\t\tnum_stripes %v sub_stripes %v\n",
- body.Head.NumStripes, body.Head.SubStripes)
- for i, stripe := range body.Stripes {
- textui.Fprintf(out, "\t\t\tstripe %v devid %d offset %d\n",
- i, stripe.DeviceID, stripe.Offset)
- textui.Fprintf(out, "\t\t\tdev_uuid %v\n",
- stripe.DeviceUUID)
- }
- case *btrfsitem.Dev:
- textui.Fprintf(out, ""+
- "\t\tdevid %d total_bytes %v bytes_used %v\n"+
- "\t\tio_align %v io_width %v sector_size %v type %v\n"+
- "\t\tgeneration %v start_offset %v dev_group %v\n"+
- "\t\tseek_speed %v bandwidth %v\n"+
- "\t\tuuid %v\n"+
- "\t\tfsid %v\n",
- body.DevID, body.NumBytes, body.NumBytesUsed,
- body.IOOptimalAlign, body.IOOptimalWidth, body.IOMinSize, body.Type,
- body.Generation, body.StartOffset, body.DevGroup,
- body.SeekSpeed, body.Bandwidth,
- body.DevUUID,
- body.FSUUID)
- case *btrfsitem.DevExtent:
- textui.Fprintf(out, ""+
- "\t\tdev extent chunk_tree %d\n"+
- "\t\tchunk_objectid %v chunk_offset %d length %d\n"+
- "\t\tchunk_tree_uuid %v\n",
- body.ChunkTree, body.ChunkObjectID, body.ChunkOffset, body.Length,
- body.ChunkTreeUUID)
- case *btrfsitem.QGroupStatus:
- textui.Fprintf(out, ""+
- "\t\tversion %v generation %v flags %v scan %d\n",
- body.Version, body.Generation, body.Flags, body.RescanProgress)
- case *btrfsitem.QGroupInfo:
- textui.Fprintf(out, ""+
- "\t\tgeneration %v\n"+
- "\t\treferenced %d referenced_compressed %d\n"+
- "\t\texclusive %d exclusive_compressed %d\n",
- body.Generation,
- body.ReferencedBytes, body.ReferencedBytesCompressed,
- body.ExclusiveBytes, body.ExclusiveBytesCompressed)
- case *btrfsitem.QGroupLimit:
- textui.Fprintf(out, ""+
- "\t\tflags %x\n"+
- "\t\tmax_referenced %d max_exclusive %d\n"+
- "\t\trsv_referenced %d rsv_exclusive %d\n",
- uint64(body.Flags),
- body.MaxReferenced, body.MaxExclusive,
- body.RsvReferenced, body.RsvExclusive)
- case *btrfsitem.UUIDMap:
- textui.Fprintf(out, "\t\tsubvol_id %d\n", body.ObjID)
- // case btrfsitem.STRING_ITEM_KEY:
- // // TODO
- case *btrfsitem.DevStats:
- textui.Fprintf(out, "\t\tpersistent item objectid %v offset %v\n",
- item.Key.ObjectID.Format(treeID), item.Key.Offset)
- switch item.Key.ObjectID {
- case btrfsprim.DEV_STATS_OBJECTID:
- textui.Fprintf(out, "\t\tdevice stats\n")
- textui.Fprintf(out, "\t\twrite_errs %v read_errs %v flush_errs %v corruption_errs %v generation %v\n",
- body.Values[btrfsitem.DEV_STAT_WRITE_ERRS],
- body.Values[btrfsitem.DEV_STAT_READ_ERRS],
- body.Values[btrfsitem.DEV_STAT_FLUSH_ERRS],
- body.Values[btrfsitem.DEV_STAT_CORRUPTION_ERRS],
- body.Values[btrfsitem.DEV_STAT_GENERATION_ERRS])
- default:
- textui.Fprintf(out, "\t\tunknown persistent item objectid %v\n", item.Key.ObjectID)
- }
- // case btrfsitem.TEMPORARY_ITEM_KEY:
- // // TODO
- case *btrfsitem.Empty:
- switch item.Key.ItemType {
- case btrfsitem.ORPHAN_ITEM_KEY: // 48
- textui.Fprintf(out, "\t\torphan item\n")
- case btrfsitem.TREE_BLOCK_REF_KEY: // 176
- textui.Fprintf(out, "\t\ttree block backref\n")
- case btrfsitem.SHARED_BLOCK_REF_KEY: // 182
- textui.Fprintf(out, "\t\tshared block backref\n")
- case btrfsitem.FREE_SPACE_EXTENT_KEY: // 199
- textui.Fprintf(out, "\t\tfree space extent\n")
- case btrfsitem.QGROUP_RELATION_KEY: // 246
- // do nothing
- // case btrfsitem.EXTENT_REF_V0_KEY:
- // textui.Fprintf(out, "\t\textent ref v0 (deprecated)\n")
- // case btrfsitem.CSUM_ITEM_KEY:
- // textui.Fprintf(out, "\t\tcsum item\n")
- default:
- textui.Fprintf(out, "\t\t(error) unhandled empty item type: %v\n", item.Key.ItemType)
- }
- case *btrfsitem.Error:
- textui.Fprintf(out, "\t\t(error) error item: %v\n", body.Err)
- default:
- textui.Fprintf(out, "\t\t(error) unhandled item type: %T\n", body)
- }
- return nil
- },
- }
- handlers.BadItem = handlers.Item
- fs.TreeWalk(
- ctx,
- treeID,
- func(err *btrfstree.TreeError) {
- dlog.Error(ctx, err)
- },
- handlers,
- )
-}
-
-// printHeaderInfo mimics btrfs-progs kernel-shared/print-tree.c:print_header_info()
-func printHeaderInfo(out io.Writer, node btrfstree.Node) {
- var typename string
- if node.Head.Level > 0 { // internal node
- typename = "node"
- textui.Fprintf(out, "node %v level %v items %v free space %v",
- node.Head.Addr,
- node.Head.Level,
- node.Head.NumItems,
- node.MaxItems()-node.Head.NumItems)
- } else { // leaf node
- typename = "leaf"
- textui.Fprintf(out, "leaf %d items %v free space %v",
- node.Head.Addr,
- node.Head.NumItems,
- node.LeafFreeSpace())
- }
- textui.Fprintf(out, " generation %v owner %v\n",
- node.Head.Generation,
- node.Head.Owner)
-
- textui.Fprintf(out, "%v %d flags %v backref revision %v\n",
- typename,
- node.Head.Addr,
- node.Head.Flags,
- node.Head.BackrefRev)
-
- textui.Fprintf(out, "checksum stored %v\n", node.Head.Checksum.Fmt(node.ChecksumType))
- if calcSum, err := node.CalculateChecksum(); err != nil {
- textui.Fprintf(out, "checksum calced %v\n", err)
- } else {
- textui.Fprintf(out, "checksum calced %v\n", calcSum.Fmt(node.ChecksumType))
- }
-
- textui.Fprintf(out, "fs uuid %v\n", node.Head.MetadataUUID)
- textui.Fprintf(out, "chunk uuid %v\n", node.Head.ChunkTreeUUID)
-}
-
-// printExtentInlineRefs mimics part of btrfs-progs kernel-shared/print-tree.c:print_extent_item()
-func printExtentInlineRefs(out io.Writer, refs []btrfsitem.ExtentInlineRef) {
- for _, ref := range refs {
- switch subitem := ref.Body.(type) {
- case nil:
- switch ref.Type {
- case btrfsitem.TREE_BLOCK_REF_KEY:
- textui.Fprintf(out, "\t\ttree block backref root %v\n",
- btrfsprim.ObjID(ref.Offset))
- case btrfsitem.SHARED_BLOCK_REF_KEY:
- textui.Fprintf(out, "\t\tshared block backref parent %v\n",
- ref.Offset)
- default:
- textui.Fprintf(out, "\t\t(error) unexpected empty sub-item type: %v\n", ref.Type)
- }
- case *btrfsitem.ExtentDataRef:
- textui.Fprintf(out, "\t\textent data backref root %v objectid %v offset %v count %v\n",
- subitem.Root, subitem.ObjectID, subitem.Offset, subitem.Count)
- case *btrfsitem.SharedDataRef:
- textui.Fprintf(out, "\t\tshared data backref parent %v count %v\n",
- ref.Offset, subitem.Count)
- default:
- textui.Fprintf(out, "\t\t(error) unexpected sub-item type: %T\n", subitem)
- }
- }
-}
-
-func fmtTime(t btrfsprim.Time) string {
- return textui.Sprintf("%v.%v (%v)",
- t.Sec, t.NSec, t.ToStd().Format("2006-01-02 15:04:05"))
-}
diff --git a/lib/btrfsprogs/btrfsinspect/rebuildmappings/blockgroups.go b/lib/btrfsprogs/btrfsinspect/rebuildmappings/blockgroups.go
deleted file mode 100644
index 0e2d5a0..0000000
--- a/lib/btrfsprogs/btrfsinspect/rebuildmappings/blockgroups.go
+++ /dev/null
@@ -1,58 +0,0 @@
-// Copyright (C) 2022 Luke Shumaker <lukeshu@lukeshu.com>
-//
-// SPDX-License-Identifier: GPL-2.0-or-later
-
-package rebuildmappings
-
-import (
- "fmt"
- "sort"
-
- "git.lukeshu.com/btrfs-progs-ng/lib/btrfs/btrfsvol"
- "git.lukeshu.com/btrfs-progs-ng/lib/btrfsprogs/btrfsinspect"
- "git.lukeshu.com/btrfs-progs-ng/lib/containers"
- "git.lukeshu.com/btrfs-progs-ng/lib/maps"
-)
-
-type BlockGroup struct {
- LAddr btrfsvol.LogicalAddr
- Size btrfsvol.AddrDelta
- Flags btrfsvol.BlockGroupFlags
-}
-
-func DedupBlockGroups(scanResults btrfsinspect.ScanDevicesResult) (map[btrfsvol.LogicalAddr]BlockGroup, error) {
- // Dedup
- bgsSet := make(containers.Set[BlockGroup])
- for _, devResults := range scanResults {
- for _, bg := range devResults.FoundBlockGroups {
- bgsSet.Insert(BlockGroup{
- LAddr: btrfsvol.LogicalAddr(bg.Key.ObjectID),
- Size: btrfsvol.AddrDelta(bg.Key.Offset),
- Flags: bg.BG.Flags,
- })
- }
- }
-
- // Sort
- bgsOrdered := maps.Keys(bgsSet)
- sort.Slice(bgsOrdered, func(i, j int) bool {
- return bgsOrdered[i].LAddr < bgsOrdered[j].LAddr
- })
-
- // Sanity check
- var pos btrfsvol.LogicalAddr
- for _, bg := range bgsOrdered {
- if bg.LAddr < pos || bg.Size < 0 {
- return nil, fmt.Errorf("found block groups are inconsistent")
- }
- pos = bg.LAddr.Add(bg.Size)
- }
-
- // Return. We return a map instead of a slice in order to
- // facilitate easy deletes.
- bgsMap := make(map[btrfsvol.LogicalAddr]BlockGroup, len(bgsSet))
- for bg := range bgsSet {
- bgsMap[bg.LAddr] = bg
- }
- return bgsMap, nil
-}
diff --git a/lib/btrfsprogs/btrfsinspect/rebuildmappings/fuzzymatchsums.go b/lib/btrfsprogs/btrfsinspect/rebuildmappings/fuzzymatchsums.go
deleted file mode 100644
index 4724c12..0000000
--- a/lib/btrfsprogs/btrfsinspect/rebuildmappings/fuzzymatchsums.go
+++ /dev/null
@@ -1,159 +0,0 @@
-// Copyright (C) 2022-2023 Luke Shumaker <lukeshu@lukeshu.com>
-//
-// SPDX-License-Identifier: GPL-2.0-or-later
-
-package rebuildmappings
-
-import (
- "context"
- "sort"
-
- "github.com/datawire/dlib/dlog"
- "golang.org/x/text/number"
-
- "git.lukeshu.com/btrfs-progs-ng/lib/btrfs"
- "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/maps"
- "git.lukeshu.com/btrfs-progs-ng/lib/textui"
-)
-
-var minFuzzyPct = textui.Tunable(0.5)
-
-type fuzzyRecord struct {
- PAddr btrfsvol.QualifiedPhysicalAddr
- N int
-}
-
-func (a fuzzyRecord) Compare(b fuzzyRecord) int {
- switch {
- case a.N < b.N:
- return -1
- case a.N > b.N:
- return 1
- default:
- return 0
- }
-}
-
-func fuzzyMatchBlockGroupSums(ctx context.Context,
- fs *btrfs.FS,
- blockgroups map[btrfsvol.LogicalAddr]BlockGroup,
- physicalSums map[btrfsvol.DeviceID]btrfssum.SumRun[btrfsvol.PhysicalAddr],
- logicalSums SumRunWithGaps[btrfsvol.LogicalAddr],
-) error {
- _ctx := ctx
-
- ctx = dlog.WithField(_ctx, "btrfsinspect.rebuild-mappings.substep", "indexing")
- dlog.Info(ctx, "Indexing physical regions...") // O(m)
- regions := ListUnmappedPhysicalRegions(fs)
- physicalIndex := make(map[btrfssum.ShortSum][]btrfsvol.QualifiedPhysicalAddr)
- if err := WalkUnmappedPhysicalRegions(ctx, physicalSums, regions, func(devID btrfsvol.DeviceID, region btrfssum.SumRun[btrfsvol.PhysicalAddr]) error {
- return region.Walk(ctx, func(paddr btrfsvol.PhysicalAddr, sum btrfssum.ShortSum) error {
- physicalIndex[sum] = append(physicalIndex[sum], btrfsvol.QualifiedPhysicalAddr{
- Dev: devID,
- Addr: paddr,
- })
- return nil
- })
- }); err != nil {
- return err
- }
- dlog.Info(ctx, "... done indexing")
-
- ctx = dlog.WithField(_ctx, "btrfsinspect.rebuild-mappings.substep", "searching")
- dlog.Info(ctx, "Searching...")
- numBlockgroups := len(blockgroups)
- for i, bgLAddr := range maps.SortedKeys(blockgroups) {
- blockgroup := blockgroups[bgLAddr]
- bgRun := SumsForLogicalRegion(logicalSums, blockgroup.LAddr, blockgroup.Size)
-
- 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)
- for _, paddr := range physicalIndex[sum] { // …log(m)) expected but …m) worst
- key := btrfsvol.QualifiedPhysicalAddr{
- Dev: paddr.Dev,
- Addr: paddr.Addr.Add(-off),
- }
- matches[key]++
- }
- return nil
- }); err != nil {
- return err
- }
-
- best := lowestN[fuzzyRecord]{N: 2}
- for paddr, n := range matches { // O(m)
- best.Insert(fuzzyRecord{
- PAddr: paddr,
- N: d - n,
- })
- }
-
- var apply bool
- var matchesStr string
- switch len(best.Dat) {
- case 0: // can happen if there are no sums in the run
- matchesStr = ""
- case 1: // not sure how this can happen, but whatev
- pct := float64(d-best.Dat[0].N) / float64(d)
- matchesStr = textui.Sprintf("%v", number.Percent(pct))
- apply = pct > minFuzzyPct
- case 2:
- pct := float64(d-best.Dat[0].N) / float64(d)
- pct2 := float64(d-best.Dat[1].N) / float64(d)
- matchesStr = textui.Sprintf("best=%v secondbest=%v", number.Percent(pct), number.Percent(pct2))
- apply = pct > minFuzzyPct && pct2 < minFuzzyPct
- }
- lvl := dlog.LogLevelError
- if apply {
- lvl = dlog.LogLevelInfo
- }
- dlog.Logf(ctx, lvl, "(%v/%v) blockgroup[laddr=%v] matches=[%s]; bestpossible=%v (based on %v runs)",
- i+1, numBlockgroups, bgLAddr, matchesStr, number.Percent(bgRun.PctFull()), len(bgRun.Runs))
- if !apply {
- continue
- }
-
- mapping := btrfsvol.Mapping{
- LAddr: blockgroup.LAddr,
- PAddr: best.Dat[0].PAddr,
- Size: blockgroup.Size,
- SizeLocked: true,
- Flags: containers.Optional[btrfsvol.BlockGroupFlags]{
- OK: true,
- Val: blockgroup.Flags,
- },
- }
- if err := fs.LV.AddMapping(mapping); err != nil {
- dlog.Errorf(ctx, "error: %v", err)
- continue
- }
- delete(blockgroups, bgLAddr)
- }
- dlog.Info(ctx, "done searching")
-
- return nil
-}
-
-type lowestN[T containers.Ordered[T]] struct {
- N int
- Dat []T
-}
-
-func (l *lowestN[T]) Insert(v T) {
- switch {
- case len(l.Dat) < l.N:
- l.Dat = append(l.Dat, v)
- case v.Compare(l.Dat[0]) < 0:
- l.Dat[0] = v
- default:
- return
- }
- sort.Slice(l.Dat, func(i, j int) bool {
- return l.Dat[i].Compare(l.Dat[j]) < 0
- })
-}
diff --git a/lib/btrfsprogs/btrfsinspect/rebuildmappings/kmp.go b/lib/btrfsprogs/btrfsinspect/rebuildmappings/kmp.go
deleted file mode 100644
index 20772ba..0000000
--- a/lib/btrfsprogs/btrfsinspect/rebuildmappings/kmp.go
+++ /dev/null
@@ -1,113 +0,0 @@
-// Copyright (C) 2022-2023 Luke Shumaker <lukeshu@lukeshu.com>
-//
-// SPDX-License-Identifier: GPL-2.0-or-later
-
-package rebuildmappings
-
-import (
- "errors"
-
- "git.lukeshu.com/btrfs-progs-ng/lib/diskio"
-)
-
-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 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
-}
-
-// 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 | ~int, V comparable](substr kmpPattern[K, V]) []K {
- substrLen := substr.PatLen()
-
- 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 && !kmpSelfEq(substr, j, val) {
- val = table[val-1]
- }
- // is a match; go forward
- if kmpSelfEq(substr, val, j) {
- val++
- }
- table[j] = val
- }
- return table
-}
-
-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'.
-//
-// 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 | ~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"))
- }
-
- var matches []K
- var curMatchBeg K
- var curMatchLen K
-
- strLen := str.SeqLen()
- for pos := K(0); pos < strLen; pos++ {
- chr := str.SeqGet(pos)
-
- // Consider 'chr'
- for curMatchLen > 0 && !kmpEq(chr, substr, curMatchLen) { // shorten the match
- overlap := table[curMatchLen-1]
- curMatchBeg += curMatchLen - overlap
- curMatchLen = overlap
- }
- if kmpEq(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
- }
- }
- }
- return matches
-}
diff --git a/lib/btrfsprogs/btrfsinspect/rebuildmappings/kmp_test.go b/lib/btrfsprogs/btrfsinspect/rebuildmappings/kmp_test.go
deleted file mode 100644
index acec9b8..0000000
--- a/lib/btrfsprogs/btrfsinspect/rebuildmappings/kmp_test.go
+++ /dev/null
@@ -1,126 +0,0 @@
-// Copyright (C) 2022-2023 Luke Shumaker <lukeshu@lukeshu.com>
-//
-// SPDX-License-Identifier: GPL-2.0-or-later
-
-package rebuildmappings
-
-import (
- "bytes"
- "testing"
-
- "github.com/stretchr/testify/assert"
- "github.com/stretchr/testify/require"
-
- "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 := bytePattern[int64]([]byte("ababaa"))
- table := buildKMPTable[int64, byte](substr)
- 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 := buildKMPTable[int64, byte](bytePattern[int64](substr))
- 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 := indexAll[int64, byte](
- diskio.SliceSequence[int64, byte](str),
- bytePattern[int64](substr))
- assert.Equal(t, exp, act)
- })
-}
-
-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 := indexAll[int64, byte](
- diskio.StringSequence[int64](tc.InStr),
- bytePattern[int64](tc.InSubstr))
- assert.Equal(t, tc.ExpMatches, matches)
- })
- }
-}
diff --git a/lib/btrfsprogs/btrfsinspect/rebuildmappings/logicalsums.go b/lib/btrfsprogs/btrfsinspect/rebuildmappings/logicalsums.go
deleted file mode 100644
index 7c02d05..0000000
--- a/lib/btrfsprogs/btrfsinspect/rebuildmappings/logicalsums.go
+++ /dev/null
@@ -1,249 +0,0 @@
-// Copyright (C) 2022-2023 Luke Shumaker <lukeshu@lukeshu.com>
-//
-// SPDX-License-Identifier: GPL-2.0-or-later
-
-package rebuildmappings
-
-import (
- "context"
- "sort"
- "strings"
-
- "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/btrfssum"
- "git.lukeshu.com/btrfs-progs-ng/lib/btrfs/btrfsvol"
- "git.lukeshu.com/btrfs-progs-ng/lib/btrfsprogs/btrfsinspect"
- "git.lukeshu.com/btrfs-progs-ng/lib/containers"
- "git.lukeshu.com/btrfs-progs-ng/lib/slices"
-)
-
-func ExtractLogicalSums(ctx context.Context, scanResults btrfsinspect.ScanDevicesResult) SumRunWithGaps[btrfsvol.LogicalAddr] {
- var records []btrfsinspect.SysExtentCSum
- for _, devResults := range scanResults {
- records = append(records, devResults.FoundExtentCSums...)
- }
- // Sort lower-generation items earlier; then sort by addr.
- sort.Slice(records, func(i, j int) bool {
- a, b := records[i], records[j]
- switch {
- case a.Generation < b.Generation:
- return true
- case a.Generation > b.Generation:
- return false
- default:
- return a.Sums.Addr < b.Sums.Addr
- }
- })
- if len(records) == 0 {
- return SumRunWithGaps[btrfsvol.LogicalAddr]{}
- }
- sumSize := records[0].Sums.ChecksumSize
-
- // Now build them in to a coherent address space.
- //
- // We can't just reverse-sort by generation to avoid mutations, because given
- //
- // gen1 AAAAAAA
- // gen2 BBBBBBBB
- // gen3 CCCCCCC
- //
- // "AAAAAAA" shouldn't be present, and if we just discard "BBBBBBBB"
- // because it conflicts with "CCCCCCC", then we would erroneously
- // include "AAAAAAA".
- addrspace := new(containers.RBTree[btrfsinspect.SysExtentCSum])
- for _, newRecord := range records {
- for {
- conflict := addrspace.Search(func(oldRecord btrfsinspect.SysExtentCSum) int {
- switch {
- case newRecord.Sums.Addr.Add(newRecord.Sums.Size()) <= oldRecord.Sums.Addr:
- // 'newRecord' is wholly to the left of 'oldRecord'.
- return -1
- case oldRecord.Sums.Addr.Add(oldRecord.Sums.Size()) <= newRecord.Sums.Addr:
- // 'oldRecord' is wholly to the left of 'newRecord'.
- return 1
- default:
- // There is some overlap.
- return 0
- }
- })
- if conflict == nil {
- // We can insert it
- addrspace.Insert(newRecord)
- break
- }
- oldRecord := conflict.Value
- if oldRecord == newRecord {
- // Duplicates are to be expected.
- break
- }
- if oldRecord.Generation < newRecord.Generation {
- // Newer generation wins.
- addrspace.Delete(conflict)
- // loop around to check for more conflicts
- continue
- }
- if oldRecord.Generation > newRecord.Generation {
- // We sorted them! This shouldn't happen.
- panic("should not happen")
- }
- // Since sums are stored multiple times (RAID?), but may
- // be split between items differently between copies, we
- // should take the union (after verifying that they
- // agree on the overlapping part).
- overlapBeg := slices.Max(
- oldRecord.Sums.Addr,
- newRecord.Sums.Addr)
- overlapEnd := slices.Min(
- oldRecord.Sums.Addr.Add(oldRecord.Sums.Size()),
- newRecord.Sums.Addr.Add(newRecord.Sums.Size()))
-
- oldOverlapBeg := int(overlapBeg.Sub(oldRecord.Sums.Addr)/btrfssum.BlockSize) * sumSize
- oldOverlapEnd := int(overlapEnd.Sub(oldRecord.Sums.Addr)/btrfssum.BlockSize) * sumSize
- oldOverlap := oldRecord.Sums.Sums[oldOverlapBeg:oldOverlapEnd]
-
- newOverlapBeg := int(overlapBeg.Sub(newRecord.Sums.Addr)/btrfssum.BlockSize) * sumSize
- newOverlapEnd := int(overlapEnd.Sub(newRecord.Sums.Addr)/btrfssum.BlockSize) * sumSize
- newOverlap := newRecord.Sums.Sums[newOverlapBeg:newOverlapEnd]
-
- if oldOverlap != newOverlap {
- dlog.Errorf(ctx, "mismatch: {gen:%v, addr:%v, size:%v} conflicts with {gen:%v, addr:%v, size:%v}",
- oldRecord.Generation, oldRecord.Sums.Addr, oldRecord.Sums.Size(),
- newRecord.Generation, newRecord.Sums.Addr, newRecord.Sums.Size())
- break
- }
- // OK, we match, so take the union.
- var prefix, suffix btrfssum.ShortSum
- switch {
- case oldRecord.Sums.Addr < overlapBeg:
- prefix = oldRecord.Sums.Sums[:oldOverlapBeg]
- case newRecord.Sums.Addr < overlapBeg:
- prefix = newRecord.Sums.Sums[:newOverlapBeg]
- }
- switch {
- case oldRecord.Sums.Addr.Add(oldRecord.Sums.Size()) > overlapEnd:
- suffix = oldRecord.Sums.Sums[oldOverlapEnd:]
- case newRecord.Sums.Addr.Add(newRecord.Sums.Size()) > overlapEnd:
- suffix = newRecord.Sums.Sums[newOverlapEnd:]
- }
- unionRecord := btrfsinspect.SysExtentCSum{
- Generation: oldRecord.Generation,
- Sums: btrfsitem.ExtentCSum{
- SumRun: btrfssum.SumRun[btrfsvol.LogicalAddr]{
- ChecksumSize: oldRecord.Sums.ChecksumSize,
- Addr: slices.Min(oldRecord.Sums.Addr, newRecord.Sums.Addr),
- Sums: prefix + oldOverlap + suffix,
- },
- },
- }
- addrspace.Delete(conflict)
- newRecord = unionRecord
- // loop around to check for more conflicts
- }
- }
-
- // Now flatten that RBTree in to a SumRunWithGaps.
- var flattened SumRunWithGaps[btrfsvol.LogicalAddr]
- var curAddr btrfsvol.LogicalAddr
- var curSums strings.Builder
- addrspace.Range(func(node *containers.RBNode[btrfsinspect.SysExtentCSum]) bool {
- curEnd := curAddr + (btrfsvol.LogicalAddr(curSums.Len()/sumSize) * btrfssum.BlockSize)
- if node.Value.Sums.Addr != curEnd {
- if curSums.Len() > 0 {
- flattened.Runs = append(flattened.Runs, btrfssum.SumRun[btrfsvol.LogicalAddr]{
- ChecksumSize: sumSize,
- Addr: curAddr,
- Sums: btrfssum.ShortSum(curSums.String()),
- })
- }
- curAddr = node.Value.Sums.Addr
- curSums.Reset()
- }
- curSums.WriteString(string(node.Value.Sums.Sums))
- return true
- })
- if curSums.Len() > 0 {
- flattened.Runs = append(flattened.Runs, btrfssum.SumRun[btrfsvol.LogicalAddr]{
- ChecksumSize: sumSize,
- Addr: curAddr,
- Sums: btrfssum.ShortSum(curSums.String()),
- })
- }
- flattened.Addr = flattened.Runs[0].Addr
- last := flattened.Runs[len(flattened.Runs)-1]
- end := last.Addr.Add(last.Size())
- flattened.Size = end.Sub(flattened.Addr)
-
- return flattened
-}
-
-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]
- var cur struct {
- Addr btrfsvol.LogicalAddr
- Size btrfsvol.AddrDelta
- }
- for _, run := range logicalSums.Runs {
- for addr := run.Addr; addr < run.Addr.Add(run.Size()); addr += btrfssum.BlockSize {
- if _, maxlen := fs.LV.Resolve(addr); maxlen < btrfssum.BlockSize {
- if cur.Size == 0 {
- cur.Addr = addr
- cur.Size = 0
- }
- cur.Size += btrfssum.BlockSize
- } else if cur.Size > 0 {
- begIdx := int(cur.Addr.Sub(run.Addr)/btrfssum.BlockSize) * run.ChecksumSize
- lenIdx := (int(cur.Size) / btrfssum.BlockSize) * run.ChecksumSize
- endIdx := begIdx + lenIdx
- ret = append(ret, btrfssum.SumRun[btrfsvol.LogicalAddr]{
- ChecksumSize: run.ChecksumSize,
- Addr: cur.Addr,
- Sums: run.Sums[begIdx:endIdx],
- })
- cur.Size = 0
- }
- }
- if cur.Size > 0 {
- begIdx := int(cur.Addr.Sub(run.Addr)/btrfssum.BlockSize) * run.ChecksumSize
- lenIdx := (int(cur.Size) / btrfssum.BlockSize) * run.ChecksumSize
- endIdx := begIdx + lenIdx
- ret = append(ret, btrfssum.SumRun[btrfsvol.LogicalAddr]{
- ChecksumSize: run.ChecksumSize,
- Addr: cur.Addr,
- Sums: run.Sums[begIdx:endIdx],
- })
- cur.Size = 0
- }
- }
- return ret
-}
-
-func SumsForLogicalRegion(sums SumRunWithGaps[btrfsvol.LogicalAddr], beg btrfsvol.LogicalAddr, size btrfsvol.AddrDelta) SumRunWithGaps[btrfsvol.LogicalAddr] {
- runs := SumRunWithGaps[btrfsvol.LogicalAddr]{
- Addr: beg,
- Size: size,
- }
- for laddr := beg; laddr < beg.Add(size); {
- run, next, ok := sums.RunForAddr(laddr)
- if !ok {
- laddr = next
- continue
- }
- off := int((laddr-run.Addr)/btrfssum.BlockSize) * run.ChecksumSize
- deltaAddr := slices.Min[btrfsvol.AddrDelta](
- size-laddr.Sub(beg),
- btrfsvol.AddrDelta((len(run.Sums)-off)/run.ChecksumSize)*btrfssum.BlockSize)
- deltaOff := int(deltaAddr/btrfssum.BlockSize) * run.ChecksumSize
- runs.Runs = append(runs.Runs, btrfssum.SumRun[btrfsvol.LogicalAddr]{
- ChecksumSize: run.ChecksumSize,
- Addr: laddr,
- Sums: run.Sums[off : off+deltaOff],
- })
- laddr = laddr.Add(deltaAddr)
- }
- return runs
-}
diff --git a/lib/btrfsprogs/btrfsinspect/rebuildmappings/matchsums.go b/lib/btrfsprogs/btrfsinspect/rebuildmappings/matchsums.go
deleted file mode 100644
index a3e724e..0000000
--- a/lib/btrfsprogs/btrfsinspect/rebuildmappings/matchsums.go
+++ /dev/null
@@ -1,78 +0,0 @@
-// Copyright (C) 2022-2023 Luke Shumaker <lukeshu@lukeshu.com>
-//
-// SPDX-License-Identifier: GPL-2.0-or-later
-
-package rebuildmappings
-
-import (
- "context"
-
- "github.com/datawire/dlib/dlog"
- "golang.org/x/text/number"
-
- "git.lukeshu.com/btrfs-progs-ng/lib/btrfs"
- "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/maps"
-)
-
-func matchBlockGroupSums(ctx context.Context,
- fs *btrfs.FS,
- blockgroups map[btrfsvol.LogicalAddr]BlockGroup,
- physicalSums map[btrfsvol.DeviceID]btrfssum.SumRun[btrfsvol.PhysicalAddr],
- logicalSums SumRunWithGaps[btrfsvol.LogicalAddr],
-) error {
- regions := ListUnmappedPhysicalRegions(fs)
- numBlockgroups := len(blockgroups)
- for i, bgLAddr := range maps.SortedKeys(blockgroups) {
- blockgroup := blockgroups[bgLAddr]
- bgRun := SumsForLogicalRegion(logicalSums, blockgroup.LAddr, blockgroup.Size)
- if len(bgRun.Runs) == 0 {
- dlog.Errorf(ctx, "(%v/%v) blockgroup[laddr=%v] can't be matched because it has 0 runs",
- i+1, numBlockgroups, bgLAddr)
- continue
- }
-
- var matches []btrfsvol.QualifiedPhysicalAddr
- if err := WalkUnmappedPhysicalRegions(ctx, physicalSums, regions, func(devID btrfsvol.DeviceID, region btrfssum.SumRun[btrfsvol.PhysicalAddr]) error {
- rawMatches := indexAll[int, btrfssum.ShortSum](region, bgRun)
- for _, match := range rawMatches {
- matches = append(matches, btrfsvol.QualifiedPhysicalAddr{
- Dev: devID,
- Addr: region.Addr + (btrfsvol.PhysicalAddr(match) * btrfssum.BlockSize),
- })
- }
- return nil
- }); err != nil {
- return err
- }
-
- lvl := dlog.LogLevelError
- if len(matches) == 1 {
- lvl = dlog.LogLevelInfo
- }
- dlog.Logf(ctx, lvl, "(%v/%v) blockgroup[laddr=%v] has %v matches based on %v coverage from %v runs",
- i+1, numBlockgroups, bgLAddr, len(matches), number.Percent(bgRun.PctFull()), len(bgRun.Runs))
- if len(matches) != 1 {
- continue
- }
-
- mapping := btrfsvol.Mapping{
- LAddr: blockgroup.LAddr,
- PAddr: matches[0],
- Size: blockgroup.Size,
- SizeLocked: true,
- Flags: containers.Optional[btrfsvol.BlockGroupFlags]{
- OK: true,
- Val: blockgroup.Flags,
- },
- }
- if err := fs.LV.AddMapping(mapping); err != nil {
- dlog.Errorf(ctx, "error: %v", err)
- continue
- }
- delete(blockgroups, bgLAddr)
- }
- return nil
-}
diff --git a/lib/btrfsprogs/btrfsinspect/rebuildmappings/physicalsums.go b/lib/btrfsprogs/btrfsinspect/rebuildmappings/physicalsums.go
deleted file mode 100644
index da22fbf..0000000
--- a/lib/btrfsprogs/btrfsinspect/rebuildmappings/physicalsums.go
+++ /dev/null
@@ -1,89 +0,0 @@
-// Copyright (C) 2022-2023 Luke Shumaker <lukeshu@lukeshu.com>
-//
-// SPDX-License-Identifier: GPL-2.0-or-later
-
-package rebuildmappings
-
-import (
- "context"
- "sort"
-
- "golang.org/x/exp/constraints"
-
- "git.lukeshu.com/btrfs-progs-ng/lib/btrfs"
- "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/btrfsprogs/btrfsinspect"
- "git.lukeshu.com/btrfs-progs-ng/lib/maps"
-)
-
-func ExtractPhysicalSums(scanResults btrfsinspect.ScanDevicesResult) map[btrfsvol.DeviceID]btrfssum.SumRun[btrfsvol.PhysicalAddr] {
- ret := make(map[btrfsvol.DeviceID]btrfssum.SumRun[btrfsvol.PhysicalAddr], len(scanResults))
- for devID, devResults := range scanResults {
- ret[devID] = devResults.Checksums
- }
- return ret
-}
-
-type PhysicalRegion struct {
- Beg, End btrfsvol.PhysicalAddr
-}
-
-func ListUnmappedPhysicalRegions(fs *btrfs.FS) map[btrfsvol.DeviceID][]PhysicalRegion {
- regions := make(map[btrfsvol.DeviceID][]PhysicalRegion)
- pos := make(map[btrfsvol.DeviceID]btrfsvol.PhysicalAddr)
- mappings := fs.LV.Mappings()
- sort.Slice(mappings, func(i, j int) bool {
- return mappings[i].PAddr.Compare(mappings[j].PAddr) < 0
- })
- for _, mapping := range mappings {
- if pos[mapping.PAddr.Dev] < mapping.PAddr.Addr {
- regions[mapping.PAddr.Dev] = append(regions[mapping.PAddr.Dev], PhysicalRegion{
- Beg: pos[mapping.PAddr.Dev],
- End: mapping.PAddr.Addr,
- })
- }
- if pos[mapping.PAddr.Dev] < mapping.PAddr.Addr.Add(mapping.Size) {
- pos[mapping.PAddr.Dev] = mapping.PAddr.Addr.Add(mapping.Size)
- }
- }
- for devID, dev := range fs.LV.PhysicalVolumes() {
- devSize := dev.Size()
- if pos[devID] < devSize {
- regions[devID] = append(regions[devID], PhysicalRegion{
- Beg: pos[devID],
- End: devSize,
- })
- }
- }
- return regions
-}
-
-func roundUp[T constraints.Integer](x, multiple T) T {
- return ((x + multiple - 1) / multiple) * multiple
-}
-
-func WalkUnmappedPhysicalRegions(ctx context.Context,
- physicalSums map[btrfsvol.DeviceID]btrfssum.SumRun[btrfsvol.PhysicalAddr],
- gaps map[btrfsvol.DeviceID][]PhysicalRegion,
- fn func(btrfsvol.DeviceID, btrfssum.SumRun[btrfsvol.PhysicalAddr]) error,
-) error {
- for _, devID := range maps.SortedKeys(gaps) {
- for _, gap := range gaps[devID] {
- if err := ctx.Err(); err != nil {
- return err
- }
- begAddr := roundUp(gap.Beg, btrfssum.BlockSize)
- begOff := int(begAddr/btrfssum.BlockSize) * physicalSums[devID].ChecksumSize
- endOff := int(gap.End/btrfssum.BlockSize) * physicalSums[devID].ChecksumSize
- if err := fn(devID, btrfssum.SumRun[btrfsvol.PhysicalAddr]{
- ChecksumSize: physicalSums[devID].ChecksumSize,
- Addr: begAddr,
- Sums: physicalSums[devID].Sums[begOff:endOff],
- }); err != nil {
- return err
- }
- }
- }
- return nil
-}
diff --git a/lib/btrfsprogs/btrfsinspect/rebuildmappings/rebuildmappings.go b/lib/btrfsprogs/btrfsinspect/rebuildmappings/rebuildmappings.go
deleted file mode 100644
index cdf5e5a..0000000
--- a/lib/btrfsprogs/btrfsinspect/rebuildmappings/rebuildmappings.go
+++ /dev/null
@@ -1,222 +0,0 @@
-// Copyright (C) 2022-2023 Luke Shumaker <lukeshu@lukeshu.com>
-//
-// SPDX-License-Identifier: GPL-2.0-or-later
-
-package rebuildmappings
-
-import (
- "context"
- "fmt"
-
- "github.com/datawire/dlib/dlog"
-
- "git.lukeshu.com/btrfs-progs-ng/lib/btrfs"
- "git.lukeshu.com/btrfs-progs-ng/lib/btrfs/btrfsvol"
- "git.lukeshu.com/btrfs-progs-ng/lib/btrfsprogs/btrfsinspect"
- "git.lukeshu.com/btrfs-progs-ng/lib/containers"
- "git.lukeshu.com/btrfs-progs-ng/lib/maps"
- "git.lukeshu.com/btrfs-progs-ng/lib/textui"
-)
-
-func getNodeSize(fs *btrfs.FS) (btrfsvol.AddrDelta, error) {
- sb, err := fs.Superblock()
- if err != nil {
- return 0, err
- }
- return btrfsvol.AddrDelta(sb.NodeSize), nil
-}
-
-func RebuildMappings(ctx context.Context, fs *btrfs.FS, scanResults btrfsinspect.ScanDevicesResult) error {
- nodeSize, err := getNodeSize(fs)
- if err != nil {
- return err
- }
-
- var numChunks, numDevExts, numBlockGroups, numNodes int
- devIDs := maps.SortedKeys(scanResults)
- devices := fs.LV.PhysicalVolumes()
- for _, devID := range devIDs {
- if _, ok := devices[devID]; !ok {
- return fmt.Errorf("device ID %v mentioned in scan results is not part of the filesystem", devID)
- }
- devResults := scanResults[devID]
- numChunks += len(devResults.FoundChunks)
- numDevExts += len(devResults.FoundDevExtents)
- numBlockGroups += len(devResults.FoundBlockGroups)
- for _, paddrs := range devResults.FoundNodes {
- numNodes += len(paddrs)
- }
- }
- dlog.Infof(ctx, "plan: 1/6 process %d chunks", numChunks)
- dlog.Infof(ctx, "plan: 2/6 process %d device extents", numDevExts)
- dlog.Infof(ctx, "plan: 3/6 process %d nodes", numNodes)
- dlog.Infof(ctx, "plan: 4/6 process %d block groups", numBlockGroups)
- dlog.Infof(ctx, "plan: 5/6 search for block groups in checksum map (exact)")
- dlog.Infof(ctx, "plan: 6/6 search for block groups in checksum map (fuzzy)")
-
- _ctx := ctx
- ctx = dlog.WithField(_ctx, "btrfsinspect.rebuild-mappings.step", "1/6")
- dlog.Infof(_ctx, "1/6: Processing %d chunks...", numChunks)
- for _, devID := range devIDs {
- devResults := scanResults[devID]
- for _, chunk := range devResults.FoundChunks {
- for _, mapping := range chunk.Chunk.Mappings(chunk.Key) {
- if err := fs.LV.AddMapping(mapping); err != nil {
- dlog.Errorf(ctx, "error: adding chunk: %v", err)
- }
- }
- }
- }
- dlog.Info(_ctx, "... done processing chunks")
-
- ctx = dlog.WithField(_ctx, "btrfsinspect.rebuild-mappings.step", "2/6")
- dlog.Infof(_ctx, "2/6: Processing %d device extents...", numDevExts)
- for _, devID := range devIDs {
- devResults := scanResults[devID]
- for _, ext := range devResults.FoundDevExtents {
- if err := fs.LV.AddMapping(ext.DevExt.Mapping(ext.Key)); err != nil {
- dlog.Errorf(ctx, "error: adding devext: %v", err)
- }
- }
- }
- dlog.Info(_ctx, "... done processing device extents")
-
- // 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.)
- ctx = dlog.WithField(_ctx, "btrfsinspect.rebuild-mappings.step", "3/6")
- dlog.Infof(_ctx, "3/6: Processing %d nodes...", numNodes)
- for _, devID := range devIDs {
- devResults := scanResults[devID]
- // Sort them so that progress numbers are predictable.
- for _, laddr := range maps.SortedKeys(devResults.FoundNodes) {
- for _, paddr := range devResults.FoundNodes[laddr] {
- if err := fs.LV.AddMapping(btrfsvol.Mapping{
- LAddr: laddr,
- PAddr: btrfsvol.QualifiedPhysicalAddr{
- Dev: devID,
- Addr: paddr,
- },
- Size: nodeSize,
- SizeLocked: false,
- }); err != nil {
- dlog.Errorf(ctx, "error: adding node ident: %v", err)
- }
- }
- }
- }
- dlog.Info(_ctx, "... done processing nodes")
-
- // Use block groups to add missing flags (and as a hint to
- // combine node entries).
- ctx = dlog.WithField(_ctx, "btrfsinspect.rebuild-mappings.step", "4/6")
- dlog.Infof(_ctx, "4/6: Processing %d block groups...", numBlockGroups)
- // 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?
- bgs, err := DedupBlockGroups(scanResults)
- if err != nil {
- return err
- }
- dlog.Infof(ctx, "... de-duplicated to %d block groups", len(bgs))
- for _, bgLAddr := range maps.SortedKeys(bgs) {
- bg := bgs[bgLAddr]
- otherLAddr, otherPAddr := fs.LV.ResolveAny(bg.LAddr, bg.Size)
- if otherLAddr < 0 || otherPAddr.Addr < 0 {
- dlog.Errorf(ctx, "error: could not pair blockgroup laddr=%v (size=%v flags=%v) with a mapping",
- bg.LAddr, bg.Size, bg.Flags)
- continue
- }
-
- offsetWithinChunk := otherLAddr.Sub(bg.LAddr)
- mapping := btrfsvol.Mapping{
- LAddr: bg.LAddr,
- PAddr: otherPAddr.Add(-offsetWithinChunk),
- Size: bg.Size,
- SizeLocked: true,
- Flags: containers.Optional[btrfsvol.BlockGroupFlags]{
- OK: true,
- Val: bg.Flags,
- },
- }
- if err := fs.LV.AddMapping(mapping); err != nil {
- dlog.Errorf(ctx, "error: adding flags from blockgroup: %v", err)
- continue
- }
- delete(bgs, bgLAddr)
- }
- dlog.Info(_ctx, "... done processing block groups")
-
- // More than once, I've been tempted to get rid of this exact-search step and just have the fuzzy-search step.
- // After all, looking at the timestamps in the log, it's faster per blockgroup! For some background, the big-O
- // for each (per blockgroup) looks like:
- //
- // - exact-search: O(bgSize+physicalBlocks)
- // - fuzzy-search: O(bgSize*physicalBlocks) worst-case; O(bgSize*log(physicalBlocks)) expected
- //
- // 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.
- 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)
- logicalSums := ExtractLogicalSums(ctx, scanResults)
- if err := matchBlockGroupSums(ctx, fs, bgs, physicalSums, logicalSums); err != nil {
- return err
- }
- dlog.Info(ctx, "... done searching for exact block groups")
-
- ctx = dlog.WithField(_ctx, "btrfsinspect.rebuild-mappings.step", "6/6")
- dlog.Infof(_ctx, "6/6: Searching for %d block groups in checksum map (fuzzy)...", len(bgs))
- if err := fuzzyMatchBlockGroupSums(ctx, fs, bgs, physicalSums, logicalSums); err != nil {
- return err
- }
- dlog.Info(_ctx, "... done searching for fuzzy block groups")
-
- ctx = dlog.WithField(_ctx, "btrfsinspect.rebuild-mappings.step", "report")
- dlog.Info(_ctx, "report:")
-
- unmappedPhysicalRegions := ListUnmappedPhysicalRegions(fs)
- var unmappedPhysical btrfsvol.AddrDelta
- var numUnmappedPhysical int
- for _, devRegions := range unmappedPhysicalRegions {
- numUnmappedPhysical += len(devRegions)
- for _, region := range devRegions {
- unmappedPhysical += region.End.Sub(region.Beg)
- }
- }
- dlog.Infof(ctx, "... %d of unmapped physical space (across %d regions)", textui.IEC(unmappedPhysical, "B"), numUnmappedPhysical)
-
- unmappedLogicalRegions := ListUnmappedLogicalRegions(fs, logicalSums)
- var unmappedLogical btrfsvol.AddrDelta
- for _, region := range unmappedLogicalRegions {
- unmappedLogical += region.Size()
- }
- dlog.Infof(ctx, "... %d of unmapped summed logical space (across %d regions)", textui.IEC(unmappedLogical, "B"), len(unmappedLogicalRegions))
-
- var unmappedBlockGroups btrfsvol.AddrDelta
- for _, bg := range bgs {
- unmappedBlockGroups += bg.Size
- }
- dlog.Infof(ctx, "... %d of unmapped block groups (across %d groups)", textui.IEC(unmappedBlockGroups, "B"), len(bgs))
-
- dlog.Info(_ctx, "detailed report:")
- for _, devID := range maps.SortedKeys(unmappedPhysicalRegions) {
- for _, region := range unmappedPhysicalRegions[devID] {
- dlog.Infof(ctx, "... unmapped physical region: dev=%v beg=%v end=%v (size=%v)",
- devID, region.Beg, region.End, region.End.Sub(region.Beg))
- }
- }
- for _, region := range unmappedLogicalRegions {
- dlog.Infof(ctx, "... umapped summed logical region: beg=%v end=%v (size=%v)",
- region.Addr, region.Addr.Add(region.Size()), region.Size())
- }
- for _, laddr := range maps.SortedKeys(bgs) {
- bg := bgs[laddr]
- dlog.Infof(ctx, "... umapped block group: beg=%v end=%v (size=%v) flags=%v",
- bg.LAddr, bg.LAddr.Add(bg.Size), bg.Size, bg.Flags)
- }
-
- return nil
-}
diff --git a/lib/btrfsprogs/btrfsinspect/rebuildmappings/sumrunwithgaps.go b/lib/btrfsprogs/btrfsinspect/rebuildmappings/sumrunwithgaps.go
deleted file mode 100644
index f79e2be..0000000
--- a/lib/btrfsprogs/btrfsinspect/rebuildmappings/sumrunwithgaps.go
+++ /dev/null
@@ -1,167 +0,0 @@
-// 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/slices"
-)
-
-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)
-)
-
-// 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.PatLen()
- var full int
- for _, run := range sg.Runs {
- full += run.SeqLen()
- }
- 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, bool) {
- if addr < sg.Addr || addr >= sg.Addr.Add(sg.Size) {
- return "", false
- }
- 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
- }
- })
- if !ok {
- 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 {
- for _, run := range sg.Runs {
- if err := run.Walk(ctx, fn); err != nil {
- return err
- }
- }
- return nil
-}
-
-// 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)
-}
-
-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)
- }
- })
-}
diff --git a/lib/btrfsprogs/btrfsinspect/rebuildmappings/testdata/fuzz/FuzzIndexAll/593a5dd328ee86bac6820e3f98383aebadd2af3a22aa248546a228b08451c30d b/lib/btrfsprogs/btrfsinspect/rebuildmappings/testdata/fuzz/FuzzIndexAll/593a5dd328ee86bac6820e3f98383aebadd2af3a22aa248546a228b08451c30d
deleted file mode 100644
index 9d14adf..0000000
--- a/lib/btrfsprogs/btrfsinspect/rebuildmappings/testdata/fuzz/FuzzIndexAll/593a5dd328ee86bac6820e3f98383aebadd2af3a22aa248546a228b08451c30d
+++ /dev/null
@@ -1,3 +0,0 @@
-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
deleted file mode 100644
index 269f061..0000000
--- a/lib/btrfsprogs/btrfsinspect/rebuildmappings/testdata/fuzz/FuzzIndexAll/6bd9babbebf7eb78814e1f3425bfa6ccd6bfd42824a26e8cbd63b5117934e600
+++ /dev/null
@@ -1,3 +0,0 @@
-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
deleted file mode 100644
index b8f1562..0000000
--- a/lib/btrfsprogs/btrfsinspect/rebuildmappings/testdata/fuzz/FuzzIndexAll/84ed65595ad05a58e293dbf423c1a816b697e2763a29d7c37aa476d6eef6fd60
+++ /dev/null
@@ -1,3 +0,0 @@
-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
deleted file mode 100644
index be67506..0000000
--- a/lib/btrfsprogs/btrfsinspect/rebuildmappings/testdata/fuzz/FuzzIndexAll/9be40f71bc49b1b5c3b8e08d58d0f69cc22aefb12fd9b5931e49ff0e41953738
+++ /dev/null
@@ -1,3 +0,0 @@
-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
deleted file mode 100644
index c3bfa37..0000000
--- a/lib/btrfsprogs/btrfsinspect/rebuildmappings/testdata/fuzz/FuzzIndexAll/e43317ec61b0da9627d7b2fc0237d369082a6bf5dfe39e05c113b42ff6218d5d
+++ /dev/null
@@ -1,3 +0,0 @@
-go test fuzz v1
-[]byte("\x10\x10\x15")
-[]byte("\x10\x15")
diff --git a/lib/btrfsprogs/btrfsinspect/rebuildnodes/btrees/forrest.go b/lib/btrfsprogs/btrfsinspect/rebuildnodes/btrees/forrest.go
deleted file mode 100644
index dbbc6eb..0000000
--- a/lib/btrfsprogs/btrfsinspect/rebuildnodes/btrees/forrest.go
+++ /dev/null
@@ -1,208 +0,0 @@
-// Copyright (C) 2022-2023 Luke Shumaker <lukeshu@lukeshu.com>
-//
-// SPDX-License-Identifier: GPL-2.0-or-later
-
-package btrees
-
-import (
- "context"
-
- "github.com/datawire/dlib/dlog"
-
- "git.lukeshu.com/btrfs-progs-ng/lib/btrfs/btrfsitem"
- "git.lukeshu.com/btrfs-progs-ng/lib/btrfs/btrfsprim"
- "git.lukeshu.com/btrfs-progs-ng/lib/btrfs/btrfstree"
- "git.lukeshu.com/btrfs-progs-ng/lib/btrfs/btrfsvol"
- pkggraph "git.lukeshu.com/btrfs-progs-ng/lib/btrfsprogs/btrfsinspect/rebuildnodes/graph"
- "git.lukeshu.com/btrfs-progs-ng/lib/btrfsprogs/btrfsinspect/rebuildnodes/keyio"
- "git.lukeshu.com/btrfs-progs-ng/lib/containers"
- "git.lukeshu.com/btrfs-progs-ng/lib/slices"
- "git.lukeshu.com/btrfs-progs-ng/lib/textui"
-)
-
-type Callbacks interface {
- AddedItem(ctx context.Context, tree btrfsprim.ObjID, key btrfsprim.Key)
- AddedRoot(ctx context.Context, tree btrfsprim.ObjID, root btrfsvol.LogicalAddr)
- LookupRoot(ctx context.Context, tree btrfsprim.ObjID) (offset btrfsprim.Generation, item btrfsitem.Root, ok bool)
- LookupUUID(ctx context.Context, uuid btrfsprim.UUID) (id btrfsprim.ObjID, ok bool)
-}
-
-// RebuiltForrest is an abstraction for rebuilding and accessing
-// potentially broken btrees.
-//
-// It is conceptually a btrfstree.TreeOperator, and adds similar
-// broken-tree handling to btrfsutil.BrokenForrest. However, the API
-// is different thant btrfstree.TreeOperator, and is much more
-// efficient than btrfsutil.BrokenForrest.
-//
-// The efficiency improvements are possible because of the API
-// differences, which are necessary for how it is used in
-// rebuildnodes:
-//
-// - it consumes an already-read graph.Graph instead of reading the
-// graph itself
-//
-// - it does not use `btrfstree.TreePath`
-//
-// - it does not keep track of errors encountered in a tree
-//
-// Additionally, it provides some functionality that
-// btrfsutil.BrokenForrest does not:
-//
-// - it provides a .LeafToRoots() method to advise on what
-// additional roots should be added
-//
-// - it provides a .COWDistance() method to compare how related two
-// trees are
-//
-// A zero RebuiltForrest is invalid; it must be initialized with
-// NewRebuiltForrest().
-type RebuiltForrest struct {
- // static
- sb btrfstree.Superblock
- graph pkggraph.Graph
- keyIO *keyio.Handle
- cb Callbacks
-
- // mutable
- treesMu nestedMutex
- trees map[btrfsprim.ObjID]*RebuiltTree // must hold .treesMu to access
- leafs containers.ARCache[btrfsprim.ObjID, map[btrfsvol.LogicalAddr]containers.Set[btrfsvol.LogicalAddr]]
- incItems containers.ARCache[btrfsprim.ObjID, *itemIndex]
- excItems containers.ARCache[btrfsprim.ObjID, *itemIndex]
-}
-
-// NewRebuiltForrest returns a new RebuiltForrest instance. All of
-// the callbacks must be non-nil.
-func NewRebuiltForrest(sb btrfstree.Superblock, graph pkggraph.Graph, keyIO *keyio.Handle, cb Callbacks) *RebuiltForrest {
- return &RebuiltForrest{
- sb: sb,
- graph: graph,
- keyIO: keyIO,
- cb: cb,
-
- trees: make(map[btrfsprim.ObjID]*RebuiltTree),
- leafs: containers.ARCache[btrfsprim.ObjID, map[btrfsvol.LogicalAddr]containers.Set[btrfsvol.LogicalAddr]]{
- MaxLen: textui.Tunable(8),
- },
- incItems: containers.ARCache[btrfsprim.ObjID, *itemIndex]{
- MaxLen: textui.Tunable(8),
- },
- excItems: containers.ARCache[btrfsprim.ObjID, *itemIndex]{
- MaxLen: textui.Tunable(8),
- },
- }
-}
-
-// Tree returns a given tree, initializing it if nescessary. If it is
-// unable to initialize the tree, then nil is returned, and nothing is
-// done to the forrest.
-//
-// The tree is initialized with the normal root node of the tree.
-func (ts *RebuiltForrest) Tree(ctx context.Context, treeID btrfsprim.ObjID) *RebuiltTree {
- ctx = ts.treesMu.Lock(ctx)
- defer ts.treesMu.Unlock()
- if !ts.addTree(ctx, treeID, nil) {
- return nil
- }
- return ts.trees[treeID]
-}
-
-func (ts *RebuiltForrest) addTree(ctx context.Context, treeID btrfsprim.ObjID, stack []btrfsprim.ObjID) (ok bool) {
- if tree, ok := ts.trees[treeID]; ok {
- return tree != nil
- }
- defer func() {
- if !ok {
- // Store a negative cache of this. tree.AddRoot() for the ROOT or UUID
- // trees will call .flushNegativeCache().
- ts.trees[treeID] = nil
- }
- }()
- stack = append(stack, treeID)
- ctx = dlog.WithField(ctx, "btrfsinspect.rebuild-nodes.rebuild.add-tree", stack)
- dlog.Info(ctx, "adding tree...")
- if slices.Contains(treeID, stack[:len(stack)-1]) {
- dlog.Errorf(ctx, "failed to add tree: loop detected: %v", stack)
- return false
- }
-
- tree := &RebuiltTree{
- ID: treeID,
- Roots: make(containers.Set[btrfsvol.LogicalAddr]),
- forrest: ts,
- }
- var root btrfsvol.LogicalAddr
- switch treeID {
- case btrfsprim.ROOT_TREE_OBJECTID:
- root = ts.sb.RootTree
- case btrfsprim.CHUNK_TREE_OBJECTID:
- root = ts.sb.ChunkTree
- case btrfsprim.TREE_LOG_OBJECTID:
- root = ts.sb.LogTree
- case btrfsprim.BLOCK_GROUP_TREE_OBJECTID:
- root = ts.sb.BlockGroupRoot
- default:
- if !ts.addTree(ctx, btrfsprim.ROOT_TREE_OBJECTID, stack) {
- dlog.Error(ctx, "failed to add tree: add ROOT_TREE")
- return false
- }
- rootOff, rootItem, ok := ts.cb.LookupRoot(ctx, treeID)
- if !ok {
- dlog.Error(ctx, "failed to add tree: lookup ROOT_ITEM")
- return false
- }
- root = rootItem.ByteNr
- tree.UUID = rootItem.UUID
- if rootItem.ParentUUID != (btrfsprim.UUID{}) {
- tree.ParentGen = rootOff
- if !ts.addTree(ctx, btrfsprim.UUID_TREE_OBJECTID, stack) {
- return false
- }
- parentID, ok := ts.cb.LookupUUID(ctx, rootItem.ParentUUID)
- if !ok {
- dlog.Error(ctx, "failed to add tree: lookup UUID")
- return false
- }
- if !ts.addTree(ctx, parentID, stack) {
- dlog.Error(ctx, "failed to add tree: add parent tree")
- return false
- }
- tree.Parent = ts.trees[parentID]
- }
- }
-
- ts.trees[treeID] = tree
- if root != 0 {
- tree.AddRoot(ctx, root)
- }
-
- return true
-}
-
-func (ts *RebuiltForrest) flushNegativeCache(ctx context.Context) {
- _ = ts.treesMu.Lock(ctx)
- defer ts.treesMu.Unlock()
- for treeID, tree := range ts.trees {
- if tree == nil {
- delete(ts.trees, treeID)
- }
- }
-}
-
-// ListRoots returns a listing of all initialized trees and their root
-// nodes.
-//
-// Do not mutate the set of roots for a tree; it is a pointer to the
-// RebuiltForrest's internal set!
-func (ts *RebuiltForrest) ListRoots(ctx context.Context) map[btrfsprim.ObjID]containers.Set[btrfsvol.LogicalAddr] {
- _ = ts.treesMu.Lock(ctx)
- defer ts.treesMu.Unlock()
- ret := make(map[btrfsprim.ObjID]containers.Set[btrfsvol.LogicalAddr])
- for treeID, tree := range ts.trees {
- if tree != nil {
- ret[treeID] = tree.Roots
- }
- }
- return ret
-}
diff --git a/lib/btrfsprogs/btrfsinspect/rebuildnodes/btrees/nestedlock.go b/lib/btrfsprogs/btrfsinspect/rebuildnodes/btrees/nestedlock.go
deleted file mode 100644
index c1ffa18..0000000
--- a/lib/btrfsprogs/btrfsinspect/rebuildnodes/btrees/nestedlock.go
+++ /dev/null
@@ -1,45 +0,0 @@
-// Copyright (C) 2023 Luke Shumaker <lukeshu@lukeshu.com>
-//
-// SPDX-License-Identifier: GPL-2.0-or-later
-
-package btrees
-
-import (
- "context"
- "sync"
-)
-
-// A nestedMutex is like a sync.Mutex, but while it is locked by call
-// 'A', may be simultaneously locked by subsequent calls if the
-// subsequent calls use a Context descended from the one returned by
-// the 'A' call to .Lock().
-type nestedMutex struct {
- inner sync.Mutex
- depth int
-}
-
-type nestedMutexCtxKey struct{}
-
-// Lock locks the mutex. It is invalid to use a Context returned from
-// Lock in a different goroutine than the one it was created in. It
-// is invalid to use a Context returned from Lock after the mutex has
-// subsequently become unlocked.
-func (m *nestedMutex) Lock(ctx context.Context) context.Context {
- if other, ok := ctx.Value(nestedMutexCtxKey{}).(*nestedMutex); ok && other == m {
- m.depth++
- return ctx
- }
- m.inner.Lock()
- return context.WithValue(ctx, nestedMutexCtxKey{}, m)
-}
-
-// Unlock unlocks the mutex. It is invalid to call Unlock if the
-// mutex is not already locked. It is invalid to call Unlock from
-// multiple goroutines simultaneously.
-func (m *nestedMutex) Unlock() {
- if m.depth > 0 {
- m.depth--
- } else {
- m.inner.Unlock()
- }
-}
diff --git a/lib/btrfsprogs/btrfsinspect/rebuildnodes/btrees/tree.go b/lib/btrfsprogs/btrfsinspect/rebuildnodes/btrees/tree.go
deleted file mode 100644
index 39d8871..0000000
--- a/lib/btrfsprogs/btrfsinspect/rebuildnodes/btrees/tree.go
+++ /dev/null
@@ -1,357 +0,0 @@
-// Copyright (C) 2022-2023 Luke Shumaker <lukeshu@lukeshu.com>
-//
-// SPDX-License-Identifier: GPL-2.0-or-later
-
-package btrees
-
-import (
- "context"
- "fmt"
- "sync"
- "time"
-
- "github.com/datawire/dlib/dlog"
-
- "git.lukeshu.com/btrfs-progs-ng/lib/btrfs/btrfsitem"
- "git.lukeshu.com/btrfs-progs-ng/lib/btrfs/btrfsprim"
- "git.lukeshu.com/btrfs-progs-ng/lib/btrfs/btrfsvol"
- "git.lukeshu.com/btrfs-progs-ng/lib/btrfsprogs/btrfsinspect/rebuildnodes/keyio"
- "git.lukeshu.com/btrfs-progs-ng/lib/containers"
- "git.lukeshu.com/btrfs-progs-ng/lib/maps"
- "git.lukeshu.com/btrfs-progs-ng/lib/slices"
- "git.lukeshu.com/btrfs-progs-ng/lib/textui"
-)
-
-type RebuiltTree struct {
- // static
- ID btrfsprim.ObjID
- UUID btrfsprim.UUID
- Parent *RebuiltTree
- ParentGen btrfsprim.Generation // offset of this tree's root item
- forrest *RebuiltForrest
-
- // mutable
- mu sync.RWMutex
- Roots containers.Set[btrfsvol.LogicalAddr]
- // There are 3 more mutable "members" that are protected by
- // `mu`; but they live in a shared LRUcache. They are all
- // derived from tree.Roots, which is why it's OK if they get
- // evicted.
- //
- // 1. tree.leafToRoots() = tree.forrest.leafs.Load(tree.ID)
- // 2. tree.Items() = tree.forrest.incItems.Load(tree.ID)
- // 3. tree.PotentialItems() = tree.forrest.excItems.Load(tree.ID)
-}
-
-// LRU member 1: .leafToRoots() ////////////////////////////////////////////////////////////////////////////////////////
-
-// leafToRoots returns all leafs (lvl=0) in the filesystem that pass
-// .isOwnerOK, whether or not they're in the tree.
-func (tree *RebuiltTree) leafToRoots(ctx context.Context) map[btrfsvol.LogicalAddr]containers.Set[btrfsvol.LogicalAddr] {
- return containers.LoadOrElse[btrfsprim.ObjID, map[btrfsvol.LogicalAddr]containers.Set[btrfsvol.LogicalAddr]](&tree.forrest.leafs, tree.ID, func(btrfsprim.ObjID) map[btrfsvol.LogicalAddr]containers.Set[btrfsvol.LogicalAddr] {
- ctx = dlog.WithField(ctx, "btrfsinspect.rebuild-nodes.rebuild.index-nodes", fmt.Sprintf("tree=%v", tree.ID))
-
- nodeToRoots := make(map[btrfsvol.LogicalAddr]containers.Set[btrfsvol.LogicalAddr])
-
- var stats textui.Portion[int]
- stats.D = len(tree.forrest.graph.Nodes)
- progressWriter := textui.NewProgress[textui.Portion[int]](ctx, dlog.LogLevelInfo, textui.Tunable(1*time.Second))
- progress := func() {
- stats.N = len(nodeToRoots)
- progressWriter.Set(stats)
- }
-
- progress()
- for _, node := range maps.SortedKeys(tree.forrest.graph.Nodes) {
- tree.indexNode(ctx, node, nodeToRoots, progress, nil)
- }
- progressWriter.Done()
-
- ret := make(map[btrfsvol.LogicalAddr]containers.Set[btrfsvol.LogicalAddr])
- for node, roots := range nodeToRoots {
- if tree.forrest.graph.Nodes[node].Level == 0 && len(roots) > 0 {
- ret[node] = roots
- }
- }
- return ret
- })
-}
-
-func (tree *RebuiltTree) indexNode(ctx context.Context, node btrfsvol.LogicalAddr, index map[btrfsvol.LogicalAddr]containers.Set[btrfsvol.LogicalAddr], progress func(), stack []btrfsvol.LogicalAddr) {
- defer progress()
- if err := ctx.Err(); err != nil {
- return
- }
- if _, done := index[node]; done {
- return
- }
- if slices.Contains(node, stack) {
- // This is a panic because tree.forrest.graph.FinalCheck() should
- // have already checked for loops.
- panic("loop")
- }
- if !tree.isOwnerOK(tree.forrest.graph.Nodes[node].Owner, tree.forrest.graph.Nodes[node].Generation) {
- index[node] = nil
- return
- }
-
- // tree.leafToRoots
- stack = append(stack, node)
- var roots containers.Set[btrfsvol.LogicalAddr]
- for _, kp := range tree.forrest.graph.EdgesTo[node] {
- if !tree.isOwnerOK(tree.forrest.graph.Nodes[kp.FromNode].Owner, tree.forrest.graph.Nodes[kp.FromNode].Generation) {
- continue
- }
- tree.indexNode(ctx, kp.FromNode, index, progress, stack)
- if len(index[kp.FromNode]) > 0 {
- if roots == nil {
- roots = make(containers.Set[btrfsvol.LogicalAddr])
- }
- roots.InsertFrom(index[kp.FromNode])
- }
- }
- if roots == nil {
- roots = containers.NewSet[btrfsvol.LogicalAddr](node)
- }
- index[node] = roots
-}
-
-// isOwnerOK returns whether it is permissible for a node with
-// .Head.Owner=owner to be in this tree.
-func (tree *RebuiltTree) isOwnerOK(owner btrfsprim.ObjID, gen btrfsprim.Generation) bool {
- for {
- if owner == tree.ID {
- return true
- }
- if tree.Parent == nil || gen >= tree.ParentGen {
- return false
- }
- tree = tree.Parent
- }
-}
-
-// LRU members 2 and 3: .Items() and .PotentialItems() /////////////////////////////////////////////////////////////////
-
-// Items returns a map of the items contained in this tree.
-//
-// Do not mutate the returned map; it is a pointer to the
-// RebuiltTree's internal map!
-func (tree *RebuiltTree) Items(ctx context.Context) *containers.SortedMap[btrfsprim.Key, keyio.ItemPtr] {
- ctx = dlog.WithField(ctx, "btrfsinspect.rebuild-nodes.rebuild.index-inc-items", fmt.Sprintf("tree=%v", tree.ID))
- return tree.items(ctx, &tree.forrest.incItems, tree.Roots.HasAny)
-}
-
-// PotentialItems returns a map of items that could be added to this
-// tree with .AddRoot().
-//
-// Do not mutate the returned map; it is a pointer to the
-// RebuiltTree's internal map!
-func (tree *RebuiltTree) PotentialItems(ctx context.Context) *containers.SortedMap[btrfsprim.Key, keyio.ItemPtr] {
- ctx = dlog.WithField(ctx, "btrfsinspect.rebuild-nodes.rebuild.index-exc-items", fmt.Sprintf("tree=%v", tree.ID))
- return tree.items(ctx, &tree.forrest.excItems,
- func(roots containers.Set[btrfsvol.LogicalAddr]) bool {
- return !tree.Roots.HasAny(roots)
- })
-}
-
-type itemIndex = containers.SortedMap[btrfsprim.Key, keyio.ItemPtr]
-
-type itemStats struct {
- Leafs textui.Portion[int]
- NumItems int
- NumDups int
-}
-
-func (s itemStats) String() string {
- return textui.Sprintf("%v (%v items, %v dups)",
- s.Leafs, s.NumItems, s.NumDups)
-}
-
-func (tree *RebuiltTree) items(ctx context.Context, cache containers.Map[btrfsprim.ObjID, *itemIndex],
- leafFn func(roots containers.Set[btrfsvol.LogicalAddr]) bool,
-) *containers.SortedMap[btrfsprim.Key, keyio.ItemPtr] {
- tree.mu.RLock()
- defer tree.mu.RUnlock()
-
- return containers.LoadOrElse(cache, tree.ID, func(btrfsprim.ObjID) *itemIndex {
- var leafs []btrfsvol.LogicalAddr
- for leaf, roots := range tree.leafToRoots(ctx) {
- if leafFn(roots) {
- leafs = append(leafs, leaf)
- }
- }
- slices.Sort(leafs)
-
- var stats itemStats
- stats.Leafs.D = len(leafs)
- progressWriter := textui.NewProgress[itemStats](ctx, dlog.LogLevelInfo, textui.Tunable(1*time.Second))
-
- index := new(containers.SortedMap[btrfsprim.Key, keyio.ItemPtr])
- for i, leaf := range leafs {
- stats.Leafs.N = i
- progressWriter.Set(stats)
- for j, itemKey := range tree.forrest.graph.Nodes[leaf].Items {
- newPtr := keyio.ItemPtr{
- Node: leaf,
- Idx: j,
- }
- if oldPtr, exists := index.Load(itemKey); !exists {
- index.Store(itemKey, newPtr)
- stats.NumItems++
- } else {
- if tree.ShouldReplace(oldPtr.Node, newPtr.Node) {
- index.Store(itemKey, newPtr)
- }
- stats.NumDups++
- }
- progressWriter.Set(stats)
- }
- }
- if stats.Leafs.N > 0 {
- stats.Leafs.N = len(leafs)
- progressWriter.Set(stats)
- progressWriter.Done()
- }
-
- return index
- })
-}
-
-func (tree *RebuiltTree) ShouldReplace(oldNode, newNode btrfsvol.LogicalAddr) bool {
- oldDist, _ := tree.COWDistance(tree.forrest.graph.Nodes[oldNode].Owner)
- newDist, _ := tree.COWDistance(tree.forrest.graph.Nodes[newNode].Owner)
- switch {
- case newDist < oldDist:
- // Replace the old one with the new lower-dist one.
- return true
- case newDist > oldDist:
- // Retain the old lower-dist one.
- return false
- default:
- oldGen := tree.forrest.graph.Nodes[oldNode].Generation
- newGen := tree.forrest.graph.Nodes[newNode].Generation
- switch {
- case newGen > oldGen:
- // Replace the old one with the new higher-gen one.
- return true
- case newGen < oldGen:
- // Retain the old higher-gen one.
- return false
- default:
- // TODO: This is a panic because I'm not really sure what the
- // best way to handle this is, and so if this happens I want the
- // program to crash and force me to figure out how to handle it.
- panic(fmt.Errorf("dup nodes in tree=%v: old=%v=%v ; new=%v=%v",
- tree.ID,
- oldNode, tree.forrest.graph.Nodes[oldNode],
- newNode, tree.forrest.graph.Nodes[newNode]))
- }
- }
-}
-
-// .AddRoot() //////////////////////////////////////////////////////////////////////////////////////////////////////////
-
-type rootStats struct {
- Leafs textui.Portion[int]
- AddedLeafs int
- AddedItems int
-}
-
-func (s rootStats) String() string {
- return textui.Sprintf("%v (added %v leafs, added %v items)",
- s.Leafs, s.AddedLeafs, s.AddedItems)
-}
-
-// AddRoot adds an additional root node to the tree. It is useful to
-// call .AddRoot() to re-attach part of the tree that has been broken
-// off.
-func (tree *RebuiltTree) AddRoot(ctx context.Context, rootNode btrfsvol.LogicalAddr) {
- tree.mu.Lock()
- defer tree.mu.Unlock()
- ctx = dlog.WithField(ctx, "btrfsinspect.rebuild-nodes.rebuild.add-root", fmt.Sprintf("tree=%v rootNode=%v", tree.ID, rootNode))
- dlog.Info(ctx, "adding root...")
-
- leafToRoots := tree.leafToRoots(ctx)
-
- var stats rootStats
- stats.Leafs.D = len(leafToRoots)
- progressWriter := textui.NewProgress[rootStats](ctx, dlog.LogLevelInfo, textui.Tunable(1*time.Second))
- for i, leaf := range maps.SortedKeys(leafToRoots) {
- stats.Leafs.N = i
- progressWriter.Set(stats)
-
- if tree.Roots.HasAny(leafToRoots[leaf]) || !leafToRoots[leaf].Has(rootNode) {
- continue
- }
-
- stats.AddedLeafs++
- progressWriter.Set(stats)
-
- for _, itemKey := range tree.forrest.graph.Nodes[leaf].Items {
- tree.forrest.cb.AddedItem(ctx, tree.ID, itemKey)
- stats.AddedItems++
- progressWriter.Set(stats)
- }
- }
- stats.Leafs.N = len(leafToRoots)
- progressWriter.Set(stats)
- progressWriter.Done()
-
- tree.Roots.Insert(rootNode)
- tree.forrest.incItems.Delete(tree.ID) // force re-gen
- tree.forrest.excItems.Delete(tree.ID) // force re-gen
-
- if (tree.ID == btrfsprim.ROOT_TREE_OBJECTID || tree.ID == btrfsprim.UUID_TREE_OBJECTID) && stats.AddedItems > 0 {
- tree.forrest.flushNegativeCache(ctx)
- }
- tree.forrest.cb.AddedRoot(ctx, tree.ID, rootNode)
-}
-
-// main public API /////////////////////////////////////////////////////////////////////////////////////////////////////
-
-// COWDistance returns how many COW-snapshots down the 'tree' is from
-// the 'parent'.
-func (tree *RebuiltTree) COWDistance(parentID btrfsprim.ObjID) (dist int, ok bool) {
- for {
- if parentID == tree.ID {
- return dist, true
- }
- if tree.Parent == nil {
- return 0, false
- }
- tree = tree.Parent
- dist++
- }
-}
-
-// ReadItem reads an item from a tree.
-func (tree *RebuiltTree) ReadItem(ctx context.Context, key btrfsprim.Key) btrfsitem.Item {
- ptr, ok := tree.Items(ctx).Load(key)
- if !ok {
- panic(fmt.Errorf("should not happen: btrees.RebuiltTree.ReadItem called for not-included key: %v", key))
- }
- return tree.forrest.keyIO.ReadItem(ctx, ptr)
-}
-
-// LeafToRoots returns the list of potential roots (to pass to
-// .AddRoot) that include a given leaf-node.
-func (tree *RebuiltTree) LeafToRoots(ctx context.Context, leaf btrfsvol.LogicalAddr) containers.Set[btrfsvol.LogicalAddr] {
- if tree.forrest.graph.Nodes[leaf].Level != 0 {
- panic(fmt.Errorf("should not happen: (tree=%v).LeafToRoots(leaf=%v): not a leaf",
- tree.ID, leaf))
- }
- tree.mu.RLock()
- defer tree.mu.RUnlock()
- ret := make(containers.Set[btrfsvol.LogicalAddr])
- for root := range tree.leafToRoots(ctx)[leaf] {
- if tree.Roots.Has(root) {
- panic(fmt.Errorf("should not happen: (tree=%v).LeafToRoots(leaf=%v): tree contains root=%v but not leaf",
- tree.ID, leaf, root))
- }
- ret.Insert(root)
- }
- if len(ret) == 0 {
- return nil
- }
- return ret
-}
diff --git a/lib/btrfsprogs/btrfsinspect/rebuildnodes/graph/graph.go b/lib/btrfsprogs/btrfsinspect/rebuildnodes/graph/graph.go
deleted file mode 100644
index 2a97ec8..0000000
--- a/lib/btrfsprogs/btrfsinspect/rebuildnodes/graph/graph.go
+++ /dev/null
@@ -1,265 +0,0 @@
-// Copyright (C) 2022-2023 Luke Shumaker <lukeshu@lukeshu.com>
-//
-// SPDX-License-Identifier: GPL-2.0-or-later
-
-package graph
-
-import (
- "context"
- "fmt"
- "reflect"
- "time"
-
- "github.com/datawire/dlib/dlog"
-
- "git.lukeshu.com/btrfs-progs-ng/lib/btrfs/btrfsitem"
- "git.lukeshu.com/btrfs-progs-ng/lib/btrfs/btrfsprim"
- "git.lukeshu.com/btrfs-progs-ng/lib/btrfs/btrfstree"
- "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"
- "git.lukeshu.com/btrfs-progs-ng/lib/slices"
- "git.lukeshu.com/btrfs-progs-ng/lib/textui"
-)
-
-type Node struct {
- Level uint8
- Generation btrfsprim.Generation
- Owner btrfsprim.ObjID
- NumItems uint32
- MinItem btrfsprim.Key
- MaxItem btrfsprim.Key
- Items []btrfsprim.Key
-}
-
-func (n Node) String() string {
- if reflect.ValueOf(n).IsZero() {
- return "{}"
- }
- return fmt.Sprintf(`{lvl:%v, gen:%v, tree:%v, cnt:%v, min:(%v,%v,%v), max:(%v,%v,%v)}`,
- n.Level, n.Generation, n.Owner, n.NumItems,
- n.MinItem.ObjectID, n.MinItem.ItemType, n.MinItem.Offset,
- n.MaxItem.ObjectID, n.MaxItem.ItemType, n.MaxItem.Offset)
-}
-
-type Edge struct {
- // It is invalid for both 'FromRoot' and 'FromNode' to be
- // non-zero. If both are zero, then the Edge is from the
- // superblock.
- FromRoot btrfsvol.LogicalAddr
- FromNode btrfsvol.LogicalAddr
- FromItem int // only valid if one of FromRoot or FromNode is non-zero
-
- FromTree btrfsprim.ObjID
-
- ToNode btrfsvol.LogicalAddr
- ToLevel uint8
- ToKey btrfsprim.Key
- ToGeneration btrfsprim.Generation
-}
-
-func (kp Edge) String() string {
- var from string
- switch {
- case kp.FromRoot != 0:
- from = fmt.Sprintf("root@%v[%d]:%v",
- kp.FromRoot, kp.FromItem, kp.FromTree)
- case kp.FromNode != 0:
- from = fmt.Sprintf("{node:%v, tree:%v}[%d]",
- kp.FromNode, kp.FromTree, kp.FromItem)
- default:
- from = fmt.Sprintf("superblock:%v", kp.FromTree)
- }
- return fmt.Sprintf(`%s -> {n:%v,l:%v,g:%v,k:(%v,%v,%v)}`,
- from,
- kp.ToNode, kp.ToLevel, kp.ToGeneration,
- kp.ToKey.ObjectID,
- kp.ToKey.ItemType,
- kp.ToKey.Offset)
-}
-
-type Graph struct {
- Nodes map[btrfsvol.LogicalAddr]Node
- BadNodes map[btrfsvol.LogicalAddr]error
- EdgesFrom map[btrfsvol.LogicalAddr][]*Edge
- EdgesTo map[btrfsvol.LogicalAddr][]*Edge
-}
-
-func (g Graph) insertEdge(ptr *Edge) {
- if ptr.ToNode == 0 {
- panic("kp.ToNode should not be zero")
- }
- if ptr.FromRoot != 0 && ptr.FromNode != 0 {
- panic("kp.FromRoot and kp.FromNode should not both be set")
- }
- if (ptr.FromRoot == 0 && ptr.FromNode == 0) && ptr.FromItem != 0 {
- panic("kp.FromItem should only be set if either kp.FromRoot or kp.FromItem is set")
- }
- g.EdgesFrom[ptr.FromNode] = append(g.EdgesFrom[ptr.FromNode], ptr)
- g.EdgesTo[ptr.ToNode] = append(g.EdgesTo[ptr.ToNode], ptr)
-}
-
-func (g Graph) insertTreeRoot(sb btrfstree.Superblock, treeID btrfsprim.ObjID) {
- treeInfo, err := btrfstree.LookupTreeRoot(nil, sb, treeID)
- if err != nil {
- // This shouldn't ever happen for treeIDs that are
- // mentioned directly in the superblock; which are the
- // only trees for which we should call
- // .insertTreeRoot().
- panic(fmt.Errorf("LookupTreeRoot(%v): %w", treeID, err))
- }
- if treeInfo.RootNode == 0 {
- return
- }
- g.insertEdge(&Edge{
- FromTree: treeID,
- ToNode: treeInfo.RootNode,
- ToLevel: treeInfo.Level,
- ToGeneration: treeInfo.Generation,
- })
-}
-
-func New(sb btrfstree.Superblock) *Graph {
- g := &Graph{
- Nodes: make(map[btrfsvol.LogicalAddr]Node),
- BadNodes: make(map[btrfsvol.LogicalAddr]error),
- EdgesFrom: make(map[btrfsvol.LogicalAddr][]*Edge),
- EdgesTo: make(map[btrfsvol.LogicalAddr][]*Edge),
- }
-
- // These 4 trees are mentioned directly in the superblock, so
- // they are always seen.
- g.insertTreeRoot(sb, btrfsprim.ROOT_TREE_OBJECTID)
- g.insertTreeRoot(sb, btrfsprim.CHUNK_TREE_OBJECTID)
- g.insertTreeRoot(sb, btrfsprim.TREE_LOG_OBJECTID)
- g.insertTreeRoot(sb, btrfsprim.BLOCK_GROUP_TREE_OBJECTID)
-
- return g
-}
-
-func (g Graph) InsertNode(nodeRef *diskio.Ref[btrfsvol.LogicalAddr, btrfstree.Node]) {
- nodeData := Node{
- Level: nodeRef.Data.Head.Level,
- Generation: nodeRef.Data.Head.Generation,
- Owner: nodeRef.Data.Head.Owner,
- NumItems: nodeRef.Data.Head.NumItems,
- MinItem: discardOK(nodeRef.Data.MinItem()),
- MaxItem: discardOK(nodeRef.Data.MaxItem()),
- }
-
- if nodeRef.Data.Head.Level == 0 {
- cnt := 0
- for _, item := range nodeRef.Data.BodyLeaf {
- if _, ok := item.Body.(*btrfsitem.Root); ok {
- cnt++
- }
- }
- kps := make([]Edge, 0, cnt)
- keys := make([]btrfsprim.Key, len(nodeRef.Data.BodyLeaf))
- nodeData.Items = keys
- g.Nodes[nodeRef.Addr] = nodeData
- for i, item := range nodeRef.Data.BodyLeaf {
- keys[i] = item.Key
- if itemBody, ok := item.Body.(*btrfsitem.Root); ok {
- kps = append(kps, Edge{
- FromRoot: nodeRef.Addr,
- FromItem: i,
- FromTree: item.Key.ObjectID,
- ToNode: itemBody.ByteNr,
- ToLevel: itemBody.Level,
- ToGeneration: itemBody.Generation,
- })
- g.insertEdge(&kps[len(kps)-1])
- }
- }
- } else {
- g.Nodes[nodeRef.Addr] = nodeData
- kps := make([]Edge, len(nodeRef.Data.BodyInternal))
- for i, kp := range nodeRef.Data.BodyInternal {
- kps[i] = Edge{
- FromNode: nodeRef.Addr,
- FromItem: i,
- FromTree: nodeRef.Data.Head.Owner,
- ToNode: kp.BlockPtr,
- ToLevel: nodeRef.Data.Head.Level - 1,
- ToKey: kp.Key,
- ToGeneration: kp.Generation,
- }
- g.insertEdge(&kps[i])
- }
- }
-}
-
-func (g Graph) FinalCheck(ctx context.Context, fs diskio.File[btrfsvol.LogicalAddr], sb btrfstree.Superblock) error {
- var stats textui.Portion[int]
- _ctx := ctx
-
- ctx = dlog.WithField(_ctx, "btrfsinspect.rebuild-nodes.read.substep", "check-keypointers")
- dlog.Info(_ctx, "Checking keypointers for dead-ends...")
- progressWriter := textui.NewProgress[textui.Portion[int]](ctx, dlog.LogLevelInfo, textui.Tunable(1*time.Second))
- stats.D = len(g.EdgesTo)
- progressWriter.Set(stats)
- for laddr := range g.EdgesTo {
- if _, ok := g.Nodes[laddr]; !ok {
- _, err := btrfstree.ReadNode[btrfsvol.LogicalAddr](fs, sb, laddr, btrfstree.NodeExpectations{
- LAddr: containers.Optional[btrfsvol.LogicalAddr]{OK: true, Val: laddr},
- })
- if err == nil {
- progressWriter.Done()
- return fmt.Errorf("node@%v exists but was not in node scan results", laddr)
- }
- g.BadNodes[laddr] = err
- }
- stats.N++
- progressWriter.Set(stats)
- }
- progressWriter.Done()
- dlog.Info(ctx, "... done checking keypointers")
-
- ctx = dlog.WithField(_ctx, "btrfsinspect.rebuild-nodes.read.substep", "check-for-loops")
- dlog.Info(_ctx, "Checking for btree loops...")
- stats.D = len(g.Nodes)
- stats.N = 0
- progressWriter = textui.NewProgress[textui.Portion[int]](ctx, dlog.LogLevelInfo, textui.Tunable(1*time.Second))
- progressWriter.Set(stats)
- visited := make(containers.Set[btrfsvol.LogicalAddr], len(g.Nodes))
- numLoops := 0
- var checkNode func(node btrfsvol.LogicalAddr, stack []btrfsvol.LogicalAddr)
- checkNode = func(node btrfsvol.LogicalAddr, stack []btrfsvol.LogicalAddr) {
- defer func() {
- stats.N = len(visited)
- progressWriter.Set(stats)
- }()
- if visited.Has(node) {
- return
- }
- if slices.Contains(node, stack) {
- numLoops++
- dlog.Error(ctx, "loop:")
- for _, line := range g.renderLoop(append(stack, node)) {
- dlog.Errorf(ctx, " %s", line)
- }
- return
- }
- stack = append(stack, node)
- for _, kp := range g.EdgesTo[node] {
- checkNode(kp.FromNode, stack)
- }
- visited.Insert(node)
- }
- for _, node := range maps.SortedKeys(g.Nodes) {
- checkNode(node, nil)
- }
- progressWriter.Done()
- if numLoops > 0 {
- return fmt.Errorf("%d btree loops", numLoops)
- }
- dlog.Info(_ctx, "... done checking for loops")
-
- return nil
-}
-
-func discardOK[T any](val T, _ bool) T {
- return val
-}
diff --git a/lib/btrfsprogs/btrfsinspect/rebuildnodes/graph/loops.go b/lib/btrfsprogs/btrfsinspect/rebuildnodes/graph/loops.go
deleted file mode 100644
index 0e51805..0000000
--- a/lib/btrfsprogs/btrfsinspect/rebuildnodes/graph/loops.go
+++ /dev/null
@@ -1,133 +0,0 @@
-// Copyright (C) 2022 Luke Shumaker <lukeshu@lukeshu.com>
-//
-// SPDX-License-Identifier: GPL-2.0-or-later
-
-package graph
-
-import (
- "fmt"
- "strings"
-
- "github.com/datawire/dlib/derror"
-
- "git.lukeshu.com/btrfs-progs-ng/lib/btrfs/btrfsprim"
- "git.lukeshu.com/btrfs-progs-ng/lib/btrfs/btrfsvol"
-)
-
-func (g Graph) renderNode(node btrfsvol.LogicalAddr) []string {
- if node == 0 {
- return []string{"root"}
- } else if nodeData, ok := g.Nodes[node]; ok {
- return []string{
- fmt.Sprintf("{addr: %v,", node),
- fmt.Sprintf(" level: %v,", nodeData.Level),
- fmt.Sprintf(" gen: %v,", nodeData.Generation),
- fmt.Sprintf(" num_items: %v,", nodeData.NumItems),
- fmt.Sprintf(" min_item: {%d,%v,%d},",
- nodeData.MinItem.ObjectID,
- nodeData.MinItem.ItemType,
- nodeData.MinItem.Offset),
- fmt.Sprintf(" max_item: {%d,%v,%d}}",
- nodeData.MaxItem.ObjectID,
- nodeData.MaxItem.ItemType,
- nodeData.MaxItem.Offset),
- }
- } else if nodeErr, ok := g.BadNodes[node]; ok {
- return []string{
- fmt.Sprintf("{addr:%v,", node),
- fmt.Sprintf(" err:%q}", nodeErr.Error()),
- }
- } else {
- panic("should not happen")
- }
-}
-
-func (g Graph) renderEdge(kp Edge) []string {
- a := fmt.Sprintf("[%d]={", kp.FromItem)
- b := strings.Repeat(" ", len(a))
- ret := []string{
- a + fmt.Sprintf("ToNode: %v,", kp.ToNode),
- b + fmt.Sprintf("ToLevel: %v,", kp.ToLevel),
- b + fmt.Sprintf("ToGen: %v,", kp.ToGeneration),
- b + fmt.Sprintf("ToKey: {%d,%v,%d}}",
- kp.ToKey.ObjectID,
- kp.ToKey.ItemType,
- kp.ToKey.Offset),
- }
-
- var err error
- if toNode, ok := g.Nodes[kp.ToNode]; !ok {
- err = g.BadNodes[kp.ToNode]
- } else {
- err = checkNodeExpectations(kp, toNode)
- }
- if err != nil {
- c := strings.Repeat(" ", len(a)-1)
- ret = append(ret,
- c+"^",
- c+"`-err="+strings.ReplaceAll(err.Error(), "\n", "\n"+c+" "),
- )
- }
- return ret
-}
-
-func (g Graph) renderLoop(stack []btrfsvol.LogicalAddr) []string {
- var lines []string
- add := func(suffixes []string) {
- curLen := 0
- for _, line := range lines {
- if len(line) > curLen {
- curLen = len(line)
- }
- }
- for i, suffix := range suffixes {
- if len(lines) <= i {
- lines = append(lines, "")
- }
- if len(lines[i]) < curLen {
- if i == 0 {
- lines[i] += strings.Repeat("-", curLen-len(lines[i])-1) + ">"
- } else {
- lines[i] += strings.Repeat(" ", curLen-len(lines[i]))
- }
- }
- lines[i] += suffix
- }
- }
-
- for i, node := range stack {
- if i > 0 {
- for _, kp := range g.EdgesTo[node] {
- if kp.FromNode == stack[i-1] {
- add(g.renderEdge(*kp))
- break
- }
- }
- }
- add(g.renderNode(node))
- }
-
- return lines
-}
-
-func checkNodeExpectations(kp Edge, toNode Node) error {
- var errs derror.MultiError
- if toNode.Level != kp.ToLevel {
- errs = append(errs, fmt.Errorf("kp.level=%v != node.level=%v",
- kp.ToLevel, toNode.Level))
- }
- if toNode.Generation != kp.ToGeneration {
- errs = append(errs, fmt.Errorf("kp.generation=%v != node.generation=%v",
- kp.ToGeneration, toNode.Generation))
- }
- if toNode.NumItems == 0 {
- errs = append(errs, fmt.Errorf("node.num_items=0"))
- } else if kp.ToKey != (btrfsprim.Key{}) && toNode.MinItem != kp.ToKey {
- errs = append(errs, fmt.Errorf("kp.key=%v != node.items[0].key=%v",
- kp.ToKey, toNode.MinItem))
- }
- if len(errs) > 0 {
- return errs
- }
- return nil
-}
diff --git a/lib/btrfsprogs/btrfsinspect/rebuildnodes/keyio/keyio.go b/lib/btrfsprogs/btrfsinspect/rebuildnodes/keyio/keyio.go
deleted file mode 100644
index 56da32d..0000000
--- a/lib/btrfsprogs/btrfsinspect/rebuildnodes/keyio/keyio.go
+++ /dev/null
@@ -1,172 +0,0 @@
-// Copyright (C) 2022-2023 Luke Shumaker <lukeshu@lukeshu.com>
-//
-// SPDX-License-Identifier: GPL-2.0-or-later
-
-package keyio
-
-import (
- "context"
- "fmt"
- "sync"
-
- "github.com/datawire/dlib/dlog"
-
- "git.lukeshu.com/btrfs-progs-ng/lib/btrfs/btrfsitem"
- "git.lukeshu.com/btrfs-progs-ng/lib/btrfs/btrfsprim"
- "git.lukeshu.com/btrfs-progs-ng/lib/btrfs/btrfstree"
- "git.lukeshu.com/btrfs-progs-ng/lib/btrfs/btrfsvol"
- "git.lukeshu.com/btrfs-progs-ng/lib/btrfsprogs/btrfsinspect/rebuildnodes/graph"
- "git.lukeshu.com/btrfs-progs-ng/lib/containers"
- "git.lukeshu.com/btrfs-progs-ng/lib/diskio"
- "git.lukeshu.com/btrfs-progs-ng/lib/textui"
-)
-
-type ItemPtr struct {
- Node btrfsvol.LogicalAddr
- Idx int
-}
-
-func (ptr ItemPtr) String() string {
- return fmt.Sprintf("node@%v[%v]", ptr.Node, ptr.Idx)
-}
-
-type SizeAndErr struct {
- Size uint64
- Err error
-}
-
-type FlagsAndErr struct {
- NoDataSum bool
- Err error
-}
-
-type Handle struct {
- rawFile diskio.File[btrfsvol.LogicalAddr]
- sb btrfstree.Superblock
- graph graph.Graph
-
- Flags map[ItemPtr]FlagsAndErr // INODE_ITEM
- Names map[ItemPtr][]byte // DIR_INDEX
- Sizes map[ItemPtr]SizeAndErr // EXTENT_CSUM and EXTENT_DATA
-
- mu sync.Mutex
- cache containers.ARCache[btrfsvol.LogicalAddr, *diskio.Ref[btrfsvol.LogicalAddr, btrfstree.Node]]
-}
-
-func NewHandle(file diskio.File[btrfsvol.LogicalAddr], sb btrfstree.Superblock) *Handle {
- return &Handle{
- rawFile: file,
- sb: sb,
-
- Flags: make(map[ItemPtr]FlagsAndErr),
- Names: make(map[ItemPtr][]byte),
- Sizes: make(map[ItemPtr]SizeAndErr),
-
- cache: containers.ARCache[btrfsvol.LogicalAddr, *diskio.Ref[btrfsvol.LogicalAddr, btrfstree.Node]]{
- MaxLen: textui.Tunable(8),
- OnRemove: func(_ btrfsvol.LogicalAddr, nodeRef *diskio.Ref[btrfsvol.LogicalAddr, btrfstree.Node]) {
- btrfstree.FreeNodeRef(nodeRef)
- },
- },
- }
-}
-
-func (o *Handle) InsertNode(nodeRef *diskio.Ref[btrfsvol.LogicalAddr, btrfstree.Node]) {
- for i, item := range nodeRef.Data.BodyLeaf {
- ptr := ItemPtr{
- Node: nodeRef.Addr,
- Idx: i,
- }
- switch itemBody := item.Body.(type) {
- case *btrfsitem.Inode:
- o.Flags[ptr] = FlagsAndErr{
- NoDataSum: itemBody.Flags.Has(btrfsitem.INODE_NODATASUM),
- Err: nil,
- }
- case *btrfsitem.DirEntry:
- if item.Key.ItemType == btrfsprim.DIR_INDEX_KEY {
- o.Names[ptr] = append([]byte(nil), itemBody.Name...)
- }
- case *btrfsitem.ExtentCSum:
- o.Sizes[ptr] = SizeAndErr{
- Size: uint64(itemBody.Size()),
- Err: nil,
- }
- case *btrfsitem.FileExtent:
- size, err := itemBody.Size()
- o.Sizes[ptr] = SizeAndErr{
- Size: uint64(size),
- Err: err,
- }
- case *btrfsitem.Error:
- switch item.Key.ItemType {
- case btrfsprim.INODE_ITEM_KEY:
- o.Flags[ptr] = FlagsAndErr{
- Err: fmt.Errorf("error decoding item: ptr=%v (tree=%v key=%v): %w",
- ptr, nodeRef.Data.Head.Owner, item.Key, itemBody.Err),
- }
- case btrfsprim.EXTENT_CSUM_KEY, btrfsprim.EXTENT_DATA_KEY:
- o.Sizes[ptr] = SizeAndErr{
- Err: fmt.Errorf("error decoding item: ptr=%v (tree=%v key=%v): %w",
- ptr, nodeRef.Data.Head.Owner, item.Key, itemBody.Err),
- }
- }
- }
- }
-}
-
-func (o *Handle) SetGraph(graph graph.Graph) {
- o.graph = graph
-}
-
-func (o *Handle) readNode(ctx context.Context, laddr btrfsvol.LogicalAddr) *diskio.Ref[btrfsvol.LogicalAddr, btrfstree.Node] {
- if cached, ok := o.cache.Load(laddr); ok {
- dlog.Tracef(ctx, "cache-hit node@%v", laddr)
- return cached
- }
-
- graphInfo, ok := o.graph.Nodes[laddr]
- if !ok {
- panic(fmt.Errorf("should not happen: node@%v is not mentioned in the in-memory graph", laddr))
- }
-
- dlog.Debugf(ctx, "cache-miss node@%v, reading...", laddr)
- ref, err := btrfstree.ReadNode(o.rawFile, o.sb, laddr, btrfstree.NodeExpectations{
- LAddr: containers.Optional[btrfsvol.LogicalAddr]{OK: true, Val: laddr},
- Level: containers.Optional[uint8]{OK: true, Val: graphInfo.Level},
- Generation: containers.Optional[btrfsprim.Generation]{OK: true, Val: graphInfo.Generation},
- Owner: func(treeID btrfsprim.ObjID) error {
- if treeID != graphInfo.Owner {
- return fmt.Errorf("expected owner=%v but claims to have owner=%v",
- graphInfo.Owner, treeID)
- }
- return nil
- },
- MinItem: containers.Optional[btrfsprim.Key]{OK: true, Val: graphInfo.MinItem},
- MaxItem: containers.Optional[btrfsprim.Key]{OK: true, Val: graphInfo.MaxItem},
- })
- if err != nil {
- panic(fmt.Errorf("should not happen: i/o error: %w", err))
- }
-
- o.cache.Store(laddr, ref)
-
- return ref
-}
-
-func (o *Handle) ReadItem(ctx context.Context, ptr ItemPtr) btrfsitem.Item {
- o.mu.Lock()
- defer o.mu.Unlock()
- if o.graph.Nodes[ptr.Node].Level != 0 {
- panic(fmt.Errorf("should not happen: keyio.Handle.ReadItem called for non-leaf node@%v", ptr.Node))
- }
- if ptr.Idx < 0 {
- panic(fmt.Errorf("should not happen: keyio.Handle.ReadItem called for negative item index: %v", ptr.Idx))
- }
- items := o.readNode(ctx, ptr.Node).Data.BodyLeaf
- if ptr.Idx >= len(items) {
- panic(fmt.Errorf("should not happen: keyio.Handle.ReadItem called for out-of-bounds item index: index=%v len=%v",
- ptr.Idx, len(items)))
- }
- return items[ptr.Idx].Body.CloneItem()
-}
diff --git a/lib/btrfsprogs/btrfsinspect/rebuildnodes/rebuild.go b/lib/btrfsprogs/btrfsinspect/rebuildnodes/rebuild.go
deleted file mode 100644
index cf334a0..0000000
--- a/lib/btrfsprogs/btrfsinspect/rebuildnodes/rebuild.go
+++ /dev/null
@@ -1,583 +0,0 @@
-// Copyright (C) 2022-2023 Luke Shumaker <lukeshu@lukeshu.com>
-//
-// SPDX-License-Identifier: GPL-2.0-or-later
-
-package rebuildnodes
-
-import (
- "context"
- "fmt"
- "runtime"
- "sort"
- "time"
-
- "github.com/datawire/dlib/dgroup"
- "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/btrfsprim"
- "git.lukeshu.com/btrfs-progs-ng/lib/btrfs/btrfstree"
- "git.lukeshu.com/btrfs-progs-ng/lib/btrfs/btrfsvol"
- "git.lukeshu.com/btrfs-progs-ng/lib/btrfsprogs/btrfsinspect"
- "git.lukeshu.com/btrfs-progs-ng/lib/btrfsprogs/btrfsinspect/rebuildnodes/btrees"
- "git.lukeshu.com/btrfs-progs-ng/lib/btrfsprogs/btrfsinspect/rebuildnodes/graph"
- "git.lukeshu.com/btrfs-progs-ng/lib/btrfsprogs/btrfsinspect/rebuildnodes/keyio"
- "git.lukeshu.com/btrfs-progs-ng/lib/containers"
- "git.lukeshu.com/btrfs-progs-ng/lib/maps"
- "git.lukeshu.com/btrfs-progs-ng/lib/textui"
-)
-
-type keyAndTree struct {
- btrfsprim.Key
- TreeID btrfsprim.ObjID
-}
-
-func (a keyAndTree) Compare(b keyAndTree) int {
- if d := containers.NativeCompare(a.TreeID, b.TreeID); d != 0 {
- return d
- }
- return a.Key.Compare(b.Key)
-}
-
-func (o keyAndTree) String() string {
- return fmt.Sprintf("tree=%v key=%v", o.TreeID, o.Key)
-}
-
-type rebuilder struct {
- sb btrfstree.Superblock
- graph graph.Graph
- keyIO *keyio.Handle
-
- rebuilt *btrees.RebuiltForrest
-
- curKey struct {
- TreeID btrfsprim.ObjID
- Key containers.Optional[btrfsprim.Key]
- }
- treeQueue containers.Set[btrfsprim.ObjID]
- retryItemQueue map[btrfsprim.ObjID]containers.Set[keyAndTree]
- addedItemQueue containers.Set[keyAndTree]
- settledItemQueue containers.Set[keyAndTree]
- augmentQueue map[btrfsprim.ObjID]*treeAugmentQueue
- numAugments int
- numAugmentFailures int
-}
-
-type treeAugmentQueue struct {
- zero map[Want]struct{}
- single map[Want]btrfsvol.LogicalAddr
- multi map[Want]containers.Set[btrfsvol.LogicalAddr]
-}
-
-type Rebuilder interface {
- Rebuild(context.Context) error
- ListRoots(context.Context) map[btrfsprim.ObjID]containers.Set[btrfsvol.LogicalAddr]
-}
-
-func NewRebuilder(ctx context.Context, fs *btrfs.FS, nodeScanResults btrfsinspect.ScanDevicesResult) (Rebuilder, error) {
- ctx = dlog.WithField(ctx, "btrfsinspect.rebuild-nodes.step", "read-fs-data")
- sb, nodeGraph, keyIO, err := ScanDevices(ctx, fs, nodeScanResults) // ScanDevices does its own logging
- if err != nil {
- return nil, err
- }
-
- o := &rebuilder{
- sb: sb,
- graph: nodeGraph,
- keyIO: keyIO,
- }
- o.rebuilt = btrees.NewRebuiltForrest(sb, nodeGraph, keyIO, o)
- return o, nil
-}
-
-func (o *rebuilder) ListRoots(ctx context.Context) map[btrfsprim.ObjID]containers.Set[btrfsvol.LogicalAddr] {
- return o.rebuilt.ListRoots(ctx)
-}
-
-func (o *rebuilder) Rebuild(ctx context.Context) error {
- ctx = dlog.WithField(ctx, "btrfsinspect.rebuild-nodes.step", "rebuild")
-
- // Initialize
- o.retryItemQueue = make(map[btrfsprim.ObjID]containers.Set[keyAndTree])
- o.addedItemQueue = make(containers.Set[keyAndTree])
- o.settledItemQueue = make(containers.Set[keyAndTree])
- o.augmentQueue = make(map[btrfsprim.ObjID]*treeAugmentQueue)
-
- // Seed the queue
- o.treeQueue = containers.NewSet[btrfsprim.ObjID](
- btrfsprim.ROOT_TREE_OBJECTID,
- btrfsprim.CHUNK_TREE_OBJECTID,
- // btrfsprim.TREE_LOG_OBJECTID, // TODO(lukeshu): Special LOG_TREE handling
- btrfsprim.BLOCK_GROUP_TREE_OBJECTID,
- )
-
- // Run
- for passNum := 0; len(o.treeQueue) > 0 || len(o.addedItemQueue) > 0 || len(o.settledItemQueue) > 0 || len(o.augmentQueue) > 0; passNum++ {
- ctx := dlog.WithField(ctx, "btrfsinspect.rebuild-nodes.rebuild.pass", passNum)
-
- // Crawl trees (Drain o.treeQueue, fill o.addedItemQueue).
- if err := o.processTreeQueue(ctx); err != nil {
- return err
- }
- runtime.GC()
-
- if len(o.addedItemQueue) > 0 {
- // Settle items (drain o.addedItemQueue, fill o.augmentQueue and o.settledItemQueue).
- if err := o.processAddedItemQueue(ctx); err != nil {
- return err
- }
- } else {
- // Process items (drain o.settledItemQueue, fill o.augmentQueue and o.treeQueue).
- if err := o.processSettledItemQueue(ctx); err != nil {
- return err
- }
- }
- runtime.GC()
-
- // Apply augments (drain o.augmentQueue (and maybe o.retryItemQueue), fill o.addedItemQueue).
- if err := o.processAugmentQueue(ctx); err != nil {
- return err
- }
- runtime.GC()
- }
-
- return nil
-}
-
-// processTreeQueue drains o.treeQueue, filling o.addedItemQueue.
-func (o *rebuilder) processTreeQueue(ctx context.Context) error {
- ctx = dlog.WithField(ctx, "btrfsinspect.rebuild-nodes.rebuild.substep", "collect-items")
-
- queue := maps.SortedKeys(o.treeQueue)
- o.treeQueue = make(containers.Set[btrfsprim.ObjID])
-
- // Because trees can be wildly different sizes, it's impossible to have a meaningful
- // progress percentage here.
- o.curKey.Key.OK = false
- for _, o.curKey.TreeID = range queue {
- if err := ctx.Err(); err != nil {
- return err
- }
- // This will call o.AddedItem as nescessary, which
- // inserts to o.addedItemQueue.
- _ = o.rebuilt.Tree(ctx, o.curKey.TreeID)
- }
-
- return nil
-}
-
-type settleItemStats struct {
- textui.Portion[int]
- NumAugments int
- NumAugmentTrees int
-}
-
-func (s settleItemStats) String() string {
- // return textui.Sprintf("%v (queued %v augments across %v trees)",
- return textui.Sprintf("%v (aug:%v trees:%v)",
- s.Portion, s.NumAugments, s.NumAugmentTrees)
-}
-
-// processAddedItemQueue drains o.addedItemQueue, filling o.augmentQueue and o.settledItemQueue.
-func (o *rebuilder) processAddedItemQueue(ctx context.Context) error {
- ctx = dlog.WithField(ctx, "btrfsinspect.rebuild-nodes.rebuild.substep", "settle-items")
-
- queue := maps.Keys(o.addedItemQueue)
- o.addedItemQueue = make(containers.Set[keyAndTree])
- sort.Slice(queue, func(i, j int) bool {
- return queue[i].Compare(queue[j]) < 0
- })
-
- var progress settleItemStats
- progress.D = len(queue)
- progressWriter := textui.NewProgress[settleItemStats](ctx, dlog.LogLevelInfo, textui.Tunable(1*time.Second))
- ctx = dlog.WithField(ctx, "btrfsinspect.rebuild-nodes.rebuild.substep.progress", &progress)
-
- for i, key := range queue {
- progress.N = i
- progressWriter.Set(progress)
-
- ctx := dlog.WithField(ctx, "btrfsinspect.rebuild-nodes.rebuild.settle.item", key)
- tree := o.rebuilt.Tree(ctx, key.TreeID)
- incPtr, ok := tree.Items(ctx).Load(key.Key)
- if !ok {
- panic(fmt.Errorf("should not happen: failed to load already-added item: %v", key))
- }
- excPtr, ok := tree.PotentialItems(ctx).Load(key.Key)
- if ok && tree.ShouldReplace(incPtr.Node, excPtr.Node) {
- wantKey := WantWithTree{
- TreeID: key.TreeID,
- Key: wantFromKey(key.Key),
- }
- o.wantAugment(ctx, wantKey, tree.LeafToRoots(ctx, excPtr.Node))
- progress.NumAugments = o.numAugments
- progress.NumAugmentTrees = len(o.augmentQueue)
- progressWriter.Set(progress)
- } else if !handleWouldBeNoOp(key.ItemType) {
- o.settledItemQueue.Insert(key)
- }
- }
-
- progress.N = len(queue)
- progressWriter.Set(progress)
- progressWriter.Done()
- return nil
-}
-
-type processItemStats struct {
- textui.Portion[int]
- NumAugments int
- NumFailures int
- NumAugmentTrees int
-}
-
-func (s processItemStats) String() string {
- // return textui.Sprintf("%v (queued %v augments and %v failures across %v trees)",
- return textui.Sprintf("%v (aug:%v fail:%v trees:%v)",
- s.Portion, s.NumAugments, s.NumFailures, s.NumAugmentTrees)
-}
-
-// processSettledItemQueue drains o.settledItemQueue, filling o.augmentQueue and o.treeQueue.
-func (o *rebuilder) processSettledItemQueue(ctx context.Context) error {
- ctx = dlog.WithField(ctx, "btrfsinspect.rebuild-nodes.rebuild.substep", "process-items")
-
- queue := maps.Keys(o.settledItemQueue)
- o.settledItemQueue = make(containers.Set[keyAndTree])
- sort.Slice(queue, func(i, j int) bool {
- return queue[i].Compare(queue[j]) < 0
- })
-
- var progress processItemStats
- progress.D = len(queue)
- progressWriter := textui.NewProgress[processItemStats](ctx, dlog.LogLevelInfo, textui.Tunable(1*time.Second))
- ctx = dlog.WithField(ctx, "btrfsinspect.rebuild-nodes.rebuild.substep.progress", &progress)
-
- type keyAndBody struct {
- keyAndTree
- Body btrfsitem.Item
- }
- itemChan := make(chan keyAndBody, textui.Tunable(300)) // average items-per-node≈100; let's have a buffer of ~3 nodes
- grp := dgroup.NewGroup(ctx, dgroup.GroupConfig{})
- grp.Go("io", func(ctx context.Context) error {
- defer close(itemChan)
- for _, key := range queue {
- if err := ctx.Err(); err != nil {
- return err
- }
- ctx := dlog.WithField(ctx, "btrfsinspect.rebuild-nodes.rebuild.process.item", key)
- item := keyAndBody{
- keyAndTree: key,
- Body: o.rebuilt.Tree(ctx, key.TreeID).ReadItem(ctx, key.Key),
- }
- select {
- case itemChan <- item:
- case <-ctx.Done():
- }
- }
- return nil
- })
- grp.Go("cpu", func(ctx context.Context) error {
- defer progressWriter.Done()
- o.curKey.Key.OK = true
- for item := range itemChan {
- ctx := dlog.WithField(ctx, "btrfsinspect.rebuild-nodes.rebuild.process.item", item.keyAndTree)
- o.curKey.TreeID = item.TreeID
- o.curKey.Key.Val = item.Key
- handleItem(o, ctx, item.TreeID, btrfstree.Item{
- Key: item.Key,
- Body: item.Body,
- })
- item.Body.Free()
- if item.ItemType == btrfsitem.ROOT_ITEM_KEY {
- o.treeQueue.Insert(item.ObjectID)
- }
- progress.N++
- progress.NumAugments = o.numAugments
- progress.NumFailures = o.numAugmentFailures
- progress.NumAugmentTrees = len(o.augmentQueue)
- progressWriter.Set(progress)
- }
- return nil
- })
- return grp.Wait()
-}
-
-// processAugmentQueue drains o.augmentQueue (and maybe o.retryItemQueue), filling o.addedItemQueue.
-func (o *rebuilder) processAugmentQueue(ctx context.Context) error {
- ctx = dlog.WithField(ctx, "btrfsinspect.rebuild-nodes.rebuild.substep", "apply-augments")
-
- resolvedAugments := make(map[btrfsprim.ObjID]containers.Set[btrfsvol.LogicalAddr], len(o.augmentQueue))
- var progress textui.Portion[int]
- for _, treeID := range maps.SortedKeys(o.augmentQueue) {
- if err := ctx.Err(); err != nil {
- return err
- }
- ctx := dlog.WithField(ctx, "btrfsinspect.rebuild-nodes.rebuild.augment.tree", treeID)
- resolvedAugments[treeID] = o.resolveTreeAugments(ctx, treeID)
- progress.D += len(resolvedAugments[treeID])
- }
- o.augmentQueue = make(map[btrfsprim.ObjID]*treeAugmentQueue)
- o.numAugments = 0
- o.numAugmentFailures = 0
- runtime.GC()
-
- progressWriter := textui.NewProgress[textui.Portion[int]](ctx, dlog.LogLevelInfo, textui.Tunable(1*time.Second))
- ctx = dlog.WithField(ctx, "btrfsinspect.rebuild-nodes.rebuild.substep.progress", &progress)
- for _, treeID := range maps.SortedKeys(resolvedAugments) {
- ctx := dlog.WithField(ctx, "btrfsinspect.rebuild-nodes.rebuild.augment.tree", treeID)
- for _, nodeAddr := range maps.SortedKeys(resolvedAugments[treeID]) {
- if err := ctx.Err(); err != nil {
- progressWriter.Set(progress)
- progressWriter.Done()
- return err
- }
- progressWriter.Set(progress)
- // This will call o.AddedItem as nescessary, which
- // inserts to o.addedItemQueue.
- o.rebuilt.Tree(ctx, treeID).AddRoot(ctx, nodeAddr)
- progress.N++
- }
- }
- progressWriter.Set(progress)
- progressWriter.Done()
-
- return nil
-}
-
-func (o *rebuilder) enqueueRetry(ifTreeID btrfsprim.ObjID) {
- if o.curKey.Key.OK {
- if o.retryItemQueue[ifTreeID] == nil {
- o.retryItemQueue[ifTreeID] = make(containers.Set[keyAndTree])
- }
- o.retryItemQueue[ifTreeID].Insert(keyAndTree{
- TreeID: o.curKey.TreeID,
- Key: o.curKey.Key.Val,
- })
- } else {
- o.treeQueue.Insert(o.curKey.TreeID)
- }
-}
-
-func (o *rebuilder) resolveTreeAugments(ctx context.Context, treeID btrfsprim.ObjID) containers.Set[btrfsvol.LogicalAddr] {
- // Define an algorithm that takes several lists of items, and returns a
- // set of those items such that each input list contains zero or one of
- // the items from your return set. The same item may appear in multiple
- // of the input lists.
-
- type ChoiceInfo struct {
- Count int
- Distance int
- Generation btrfsprim.Generation
- }
- choices := make(map[btrfsvol.LogicalAddr]ChoiceInfo)
- // o.augmentQueue[treeID].zero is optimized storage for lists
- // with zero items. Go ahead and free that memory up.
- o.augmentQueue[treeID].zero = nil
- // o.augmentQueue[treeID].single is optimized storage for
- // lists with exactly 1 item.
- for _, choice := range o.augmentQueue[treeID].single {
- if old, ok := choices[choice]; ok {
- old.Count++
- choices[choice] = old
- } else {
- choices[choice] = ChoiceInfo{
- Count: 1,
- Distance: discardOK(o.rebuilt.Tree(ctx, treeID).COWDistance(o.graph.Nodes[choice].Owner)),
- Generation: o.graph.Nodes[choice].Generation,
- }
- }
- }
- // o.augmentQueue[treeID].multi is the main list storage.
- for _, list := range o.augmentQueue[treeID].multi {
- for choice := range list {
- if old, ok := choices[choice]; ok {
- old.Count++
- choices[choice] = old
- } else {
- choices[choice] = ChoiceInfo{
- Count: 1,
- Distance: discardOK(o.rebuilt.Tree(ctx, treeID).COWDistance(o.graph.Nodes[choice].Owner)),
- Generation: o.graph.Nodes[choice].Generation,
- }
- }
- }
- }
-
- // > Example 1: Given the input lists
- // >
- // > 0: [A, B]
- // > 2: [A, C]
- // >
- // > legal solutions would be `[]`, `[A]`, `[B]`, `[C]`, or `[B, C]`. It
- // > would not be legal to return `[A, B]` or `[A, C]`.
- //
- // > Example 2: Given the input lists
- // >
- // > 1: [A, B]
- // > 2: [A]
- // > 3: [B]
- // >
- // > legal solution would be `[]`, `[A]` or `[B]`. It would not be legal
- // > to return `[A, B]`.
- //
- // The algorithm should optimize for the following goals:
- //
- // - We prefer that each input list have an item in the return set.
- //
- // > In Example 1, while `[]`, `[B]`, and `[C]` are permissible
- // > solutions, they are not optimal, because one or both of the input
- // > lists are not represented.
- // >
- // > It may be the case that it is not possible to represent all lists
- // > in the result; in Example 2, either list 2 or list 3 must be
- // > unrepresented.
- //
- // - Each item has a non-negative scalar "distance" score, we prefer
- // lower distances. Distance scores are comparable; 0 is preferred,
- // and a distance of 4 is twice as bad as a distance of 2.
- //
- // - Each item has a "generation" score, we prefer higher generations.
- // Generation scores should not be treated as a linear scale; the
- // magnitude of deltas is meaningless; only the sign of a delta is
- // meaningful.
- //
- // > So it would be wrong to say something like
- // >
- // > desirability = (-a*distance) + (b*generation) // for some constants `a` and `b`
- // >
- // > because `generation` can't be used that way
- //
- // - We prefer items that appear in more lists over items that appear in
- // fewer lists.
- //
- // The relative priority of these 4 goals is undefined; preferably the
- // algorithm should be defined in a way that makes it easy to adjust the
- // relative priorities.
-
- ret := make(containers.Set[btrfsvol.LogicalAddr])
- illegal := make(containers.Set[btrfsvol.LogicalAddr]) // cannot-be-accepted and already-accepted
- accept := func(item btrfsvol.LogicalAddr) {
- ret.Insert(item)
- for _, list := range o.augmentQueue[treeID].multi {
- if list.Has(item) {
- illegal.InsertFrom(list)
- }
- }
- }
-
- sortedItems := maps.Keys(choices)
- sort.Slice(sortedItems, func(i, j int) bool {
- iItem, jItem := sortedItems[i], sortedItems[j]
- if choices[iItem].Count != choices[jItem].Count {
- return choices[iItem].Count > choices[jItem].Count // reverse this check; higher counts should sort lower
- }
- if choices[iItem].Distance != choices[jItem].Distance {
- return choices[iItem].Distance < choices[jItem].Distance
- }
- if choices[iItem].Generation != choices[jItem].Generation {
- return choices[iItem].Generation > choices[jItem].Generation // reverse this check; higher generations should sort lower
- }
- return iItem < jItem // laddr is as good a tiebreaker as anything
- })
- for _, item := range sortedItems {
- if !illegal.Has(item) {
- accept(item)
- }
- }
-
- // Log our result
- wantKeys := append(
- maps.Keys(o.augmentQueue[treeID].single),
- maps.Keys(o.augmentQueue[treeID].multi)...)
- sort.Slice(wantKeys, func(i, j int) bool {
- return wantKeys[i].Compare(wantKeys[j]) < 0
- })
- for _, wantKey := range wantKeys {
- list, ok := o.augmentQueue[treeID].multi[wantKey]
- if !ok {
- list = containers.NewSet[btrfsvol.LogicalAddr](o.augmentQueue[treeID].single[wantKey])
- }
- chose := list.Intersection(ret)
- switch {
- case len(chose) == 0:
- dlog.Infof(ctx, "lists[%q]: chose (none) from %v", wantKey, maps.SortedKeys(list))
- case len(list) > 1:
- dlog.Infof(ctx, "lists[%q]: chose %v from %v", wantKey, chose.TakeOne(), maps.SortedKeys(list))
- default:
- dlog.Debugf(ctx, "lists[%q]: chose %v from %v", wantKey, chose.TakeOne(), maps.SortedKeys(list))
- }
- }
-
- // Free some memory
- o.augmentQueue[treeID].single = nil
- o.augmentQueue[treeID].multi = nil
-
- return ret
-}
-
-////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
-
-func (queue *treeAugmentQueue) has(wantKey Want) bool {
- if queue != nil {
- if queue.zero != nil {
- if _, ok := queue.zero[wantKey]; ok {
- return true
- }
- }
- if queue.single != nil {
- if _, ok := queue.single[wantKey]; ok {
- return true
- }
- }
- if queue.multi != nil {
- if _, ok := queue.multi[wantKey]; ok {
- return true
- }
- }
- }
- return false
-}
-
-func (queue *treeAugmentQueue) store(wantKey Want, choices containers.Set[btrfsvol.LogicalAddr]) {
- if len(choices) == 0 && wantKey.OffsetType > offsetExact {
- // This wantKey is unlikely to come up again, so it's
- // not worth the RAM of storing a negative result.
- return
- }
- switch len(choices) {
- case 0:
- if queue.zero == nil {
- queue.zero = make(map[Want]struct{})
- }
- queue.zero[wantKey] = struct{}{}
- case 1:
- if queue.single == nil {
- queue.single = make(map[Want]btrfsvol.LogicalAddr)
- }
- queue.single[wantKey] = choices.TakeOne()
- default:
- if queue.multi == nil {
- queue.multi = make(map[Want]containers.Set[btrfsvol.LogicalAddr])
- }
- queue.multi[wantKey] = choices
- }
-}
-
-func (o *rebuilder) hasAugment(wantKey WantWithTree) bool {
- return o.augmentQueue[wantKey.TreeID].has(wantKey.Key)
-}
-
-func (o *rebuilder) wantAugment(ctx context.Context, wantKey WantWithTree, choices containers.Set[btrfsvol.LogicalAddr]) {
- if o.augmentQueue[wantKey.TreeID] == nil {
- o.augmentQueue[wantKey.TreeID] = new(treeAugmentQueue)
- }
- o.augmentQueue[wantKey.TreeID].store(wantKey.Key, choices)
- if len(choices) == 0 {
- o.numAugmentFailures++
- dlog.Debug(ctx, "ERR: could not find wanted item")
- } else {
- o.numAugments++
- dlog.Debugf(ctx, "choices=%v", maps.SortedKeys(choices))
- }
-}
diff --git a/lib/btrfsprogs/btrfsinspect/rebuildnodes/rebuild_graph.go b/lib/btrfsprogs/btrfsinspect/rebuildnodes/rebuild_graph.go
deleted file mode 100644
index 710030c..0000000
--- a/lib/btrfsprogs/btrfsinspect/rebuildnodes/rebuild_graph.go
+++ /dev/null
@@ -1,367 +0,0 @@
-// Copyright (C) 2022-2023 Luke Shumaker <lukeshu@lukeshu.com>
-//
-// SPDX-License-Identifier: GPL-2.0-or-later
-
-package rebuildnodes
-
-import (
- "context"
- "fmt"
-
- "git.lukeshu.com/btrfs-progs-ng/lib/btrfs/btrfsitem"
- "git.lukeshu.com/btrfs-progs-ng/lib/btrfs/btrfsprim"
- "git.lukeshu.com/btrfs-progs-ng/lib/btrfs/btrfstree"
- "git.lukeshu.com/btrfs-progs-ng/lib/btrfs/btrfsvol"
-)
-
-type rebuildCallbacks interface {
- fsErr(ctx context.Context, e error)
- want(ctx context.Context, reason string, treeID btrfsprim.ObjID, objID btrfsprim.ObjID, typ btrfsprim.ItemType)
- wantOff(ctx context.Context, reason string, treeID btrfsprim.ObjID, objID btrfsprim.ObjID, typ btrfsprim.ItemType, off uint64)
- wantDirIndex(ctx context.Context, reason string, treeID btrfsprim.ObjID, objID btrfsprim.ObjID, name []byte)
- wantCSum(ctx context.Context, reason string, inodeTree, inodeItem btrfsprim.ObjID, beg, end btrfsvol.LogicalAddr) // interval is [beg, end)
- wantFileExt(ctx context.Context, reason string, treeID btrfsprim.ObjID, ino btrfsprim.ObjID, size int64)
-}
-
-// handleWouldBeNoOp returns whether or not a call to handleItem for a
-// given item type would be a no-op.
-func handleWouldBeNoOp(typ btrfsprim.ItemType) bool {
- switch typ {
- case // btrfsitem.Dev
- btrfsprim.DEV_ITEM_KEY,
- // btrfsitem.DevStats
- btrfsprim.PERSISTENT_ITEM_KEY,
- // btrfsitem.Empty
- btrfsprim.ORPHAN_ITEM_KEY,
- btrfsprim.TREE_BLOCK_REF_KEY,
- btrfsprim.SHARED_BLOCK_REF_KEY,
- btrfsprim.FREE_SPACE_EXTENT_KEY,
- btrfsprim.QGROUP_RELATION_KEY,
- // btrfsite.ExtentCSum
- btrfsprim.EXTENT_CSUM_KEY:
- return true
- default:
- return false
- }
-}
-
-func handleItem(o rebuildCallbacks, ctx context.Context, treeID btrfsprim.ObjID, item btrfstree.Item) {
- // Notionally, just express the relationships shown in
- // https://btrfs.wiki.kernel.org/index.php/File:References.png (from the page
- // https://btrfs.wiki.kernel.org/index.php/Data_Structures )
- switch body := item.Body.(type) {
- case *btrfsitem.BlockGroup:
- o.want(ctx, "Chunk",
- btrfsprim.CHUNK_TREE_OBJECTID,
- body.ChunkObjectID,
- btrfsitem.CHUNK_ITEM_KEY)
- o.wantOff(ctx, "FreeSpaceInfo",
- btrfsprim.FREE_SPACE_TREE_OBJECTID,
- item.Key.ObjectID,
- btrfsitem.FREE_SPACE_INFO_KEY,
- item.Key.Offset)
- case *btrfsitem.Chunk:
- o.want(ctx, "owning Root",
- btrfsprim.ROOT_TREE_OBJECTID,
- body.Head.Owner,
- btrfsitem.ROOT_ITEM_KEY)
- case *btrfsitem.Dev:
- // nothing
- case *btrfsitem.DevExtent:
- o.wantOff(ctx, "Chunk",
- body.ChunkTree,
- body.ChunkObjectID,
- btrfsitem.CHUNK_ITEM_KEY,
- uint64(body.ChunkOffset))
- case *btrfsitem.DevStats:
- // nothing
- case *btrfsitem.DirEntry:
- // containing-directory
- o.wantOff(ctx, "containing dir inode",
- treeID,
- item.Key.ObjectID,
- btrfsitem.INODE_ITEM_KEY,
- 0)
- // siblings
- switch item.Key.ItemType {
- case btrfsitem.DIR_ITEM_KEY:
- o.wantDirIndex(ctx, "corresponding DIR_INDEX",
- treeID,
- item.Key.ObjectID,
- body.Name)
- case btrfsitem.DIR_INDEX_KEY:
- o.wantOff(ctx, "corresponding DIR_ITEM",
- treeID,
- item.Key.ObjectID,
- btrfsitem.DIR_ITEM_KEY,
- btrfsitem.NameHash(body.Name))
- case btrfsitem.XATTR_ITEM_KEY:
- // nothing
- default:
- // This is a panic because the item decoder should not emit a
- // btrfsitem.DirEntry for other item types without this code also being
- // updated.
- panic(fmt.Errorf("should not happen: DirEntry: unexpected ItemType=%v", item.Key.ItemType))
- }
- // item-within-directory
- if body.Location != (btrfsprim.Key{}) {
- switch body.Location.ItemType {
- case btrfsitem.INODE_ITEM_KEY:
- o.wantOff(ctx, "item being pointed to",
- treeID,
- body.Location.ObjectID,
- body.Location.ItemType,
- body.Location.Offset)
- o.wantOff(ctx, "backref from item being pointed to",
- treeID,
- body.Location.ObjectID,
- btrfsitem.INODE_REF_KEY,
- uint64(item.Key.ObjectID))
- case btrfsitem.ROOT_ITEM_KEY:
- o.want(ctx, "Root of subvolume being pointed to",
- btrfsprim.ROOT_TREE_OBJECTID,
- body.Location.ObjectID,
- body.Location.ItemType)
- default:
- o.fsErr(ctx, fmt.Errorf("DirEntry: unexpected .Location.ItemType=%v", body.Location.ItemType))
- }
- }
- case *btrfsitem.Empty:
- // nothing
- case *btrfsitem.Extent:
- // if body.Head.Flags.Has(btrfsitem.EXTENT_FLAG_TREE_BLOCK) {
- // // Supposedly this flag indicates that
- // // body.Info.Key identifies a node by the
- // // first key in the node. But nothing in the
- // // kernel ever reads this, so who knows if it
- // // always gets updated correctly?
- // }
- for i, ref := range body.Refs {
- switch refBody := ref.Body.(type) {
- case nil:
- // nothing
- case *btrfsitem.ExtentDataRef:
- o.wantOff(ctx, "referencing Inode",
- refBody.Root,
- refBody.ObjectID,
- btrfsitem.INODE_ITEM_KEY,
- 0)
- o.wantOff(ctx, "referencing FileExtent",
- refBody.Root,
- refBody.ObjectID,
- btrfsitem.EXTENT_DATA_KEY,
- uint64(refBody.Offset))
- case *btrfsitem.SharedDataRef:
- // nothing
- default:
- // This is a panic because the item decoder should not emit a new
- // type to ref.Body without this code also being updated.
- panic(fmt.Errorf("should not happen: Extent: unexpected .Refs[%d].Body type %T", i, refBody))
- }
- }
- case *btrfsitem.ExtentCSum:
- // nothing
- case *btrfsitem.ExtentDataRef:
- o.want(ctx, "Extent being referenced",
- btrfsprim.EXTENT_TREE_OBJECTID,
- item.Key.ObjectID,
- btrfsitem.EXTENT_ITEM_KEY)
- o.wantOff(ctx, "referencing Inode",
- body.Root,
- body.ObjectID,
- btrfsitem.INODE_ITEM_KEY,
- 0)
- o.wantOff(ctx, "referencing FileExtent",
- body.Root,
- body.ObjectID,
- btrfsitem.EXTENT_DATA_KEY,
- uint64(body.Offset))
- case *btrfsitem.FileExtent:
- o.wantOff(ctx, "containing Inode",
- treeID,
- item.Key.ObjectID,
- btrfsitem.INODE_ITEM_KEY,
- 0)
- switch body.Type {
- case btrfsitem.FILE_EXTENT_INLINE:
- // nothing
- case btrfsitem.FILE_EXTENT_REG, btrfsitem.FILE_EXTENT_PREALLOC:
- // NB: o.wantCSum checks inodeBody.Flags.Has(btrfsitem.INODE_NODATASUM) for us.
- o.wantCSum(ctx, "data sum",
- treeID, item.Key.ObjectID,
- body.BodyExtent.DiskByteNr,
- body.BodyExtent.DiskByteNr.Add(body.BodyExtent.DiskNumBytes))
- default:
- o.fsErr(ctx, fmt.Errorf("FileExtent: unexpected body.Type=%v", body.Type))
- }
- case *btrfsitem.FreeSpaceBitmap:
- o.wantOff(ctx, "FreeSpaceInfo",
- treeID,
- item.Key.ObjectID,
- btrfsitem.FREE_SPACE_INFO_KEY,
- item.Key.Offset)
- case *btrfsitem.FreeSpaceHeader:
- o.wantOff(ctx, ".Location",
- treeID,
- body.Location.ObjectID,
- body.Location.ItemType,
- body.Location.Offset)
- case *btrfsitem.FreeSpaceInfo:
- if body.Flags.Has(btrfsitem.FREE_SPACE_USING_BITMAPS) {
- o.wantOff(ctx, "FreeSpaceBitmap",
- treeID,
- item.Key.ObjectID,
- btrfsitem.FREE_SPACE_BITMAP_KEY,
- item.Key.Offset)
- }
- case *btrfsitem.Inode:
- o.want(ctx, "backrefs",
- treeID, // TODO: validate the number of these against body.NLink
- item.Key.ObjectID,
- btrfsitem.INODE_REF_KEY)
- o.wantFileExt(ctx, "FileExtents",
- treeID, item.Key.ObjectID, body.Size)
- if body.BlockGroup != 0 {
- o.want(ctx, "BlockGroup",
- btrfsprim.EXTENT_TREE_OBJECTID,
- body.BlockGroup,
- btrfsitem.BLOCK_GROUP_ITEM_KEY)
- }
- case *btrfsitem.InodeRefs:
- o.wantOff(ctx, "child Inode",
- treeID,
- item.Key.ObjectID,
- btrfsitem.INODE_ITEM_KEY,
- 0)
- o.wantOff(ctx, "parent Inode",
- treeID,
- btrfsprim.ObjID(item.Key.Offset),
- btrfsitem.INODE_ITEM_KEY,
- 0)
- for _, ref := range body.Refs {
- o.wantOff(ctx, "DIR_ITEM",
- treeID,
- btrfsprim.ObjID(item.Key.Offset),
- btrfsitem.DIR_ITEM_KEY,
- btrfsitem.NameHash(ref.Name))
- o.wantOff(ctx, "DIR_INDEX",
- treeID,
- btrfsprim.ObjID(item.Key.Offset),
- btrfsitem.DIR_INDEX_KEY,
- uint64(ref.Index))
- }
- case *btrfsitem.Metadata:
- for i, ref := range body.Refs {
- switch refBody := ref.Body.(type) {
- case nil:
- // nothing
- case *btrfsitem.ExtentDataRef:
- o.wantOff(ctx, "referencing INode",
- refBody.Root,
- refBody.ObjectID,
- btrfsitem.INODE_ITEM_KEY,
- 0)
- o.wantOff(ctx, "referencing FileExtent",
- refBody.Root,
- refBody.ObjectID,
- btrfsitem.EXTENT_DATA_KEY,
- uint64(refBody.Offset))
- case *btrfsitem.SharedDataRef:
- // nothing
- default:
- // This is a panic because the item decoder should not emit a new
- // type to ref.Body without this code also being updated.
- panic(fmt.Errorf("should not happen: Metadata: unexpected .Refs[%d].Body type %T", i, refBody))
- }
- }
- case *btrfsitem.Root:
- if body.RootDirID != 0 {
- o.wantOff(ctx, "root directory",
- item.Key.ObjectID,
- body.RootDirID,
- btrfsitem.INODE_ITEM_KEY,
- 0)
- }
- if body.UUID != (btrfsprim.UUID{}) {
- key := btrfsitem.UUIDToKey(body.UUID)
- o.wantOff(ctx, "uuid",
- btrfsprim.UUID_TREE_OBJECTID,
- key.ObjectID,
- key.ItemType,
- key.Offset)
- }
- if body.ParentUUID != (btrfsprim.UUID{}) {
- key := btrfsitem.UUIDToKey(body.ParentUUID)
- o.wantOff(ctx, "parent uuid",
- btrfsprim.UUID_TREE_OBJECTID,
- key.ObjectID,
- key.ItemType,
- key.Offset)
- }
- case *btrfsitem.RootRef:
- var otherType btrfsprim.ItemType
- var parent, child btrfsprim.ObjID
- switch item.Key.ItemType {
- case btrfsitem.ROOT_REF_KEY:
- otherType = btrfsitem.ROOT_BACKREF_KEY
- parent = item.Key.ObjectID
- child = btrfsprim.ObjID(item.Key.Offset)
- case btrfsitem.ROOT_BACKREF_KEY:
- otherType = btrfsitem.ROOT_REF_KEY
- parent = btrfsprim.ObjID(item.Key.Offset)
- child = item.Key.ObjectID
- default:
- // This is a panic because the item decoder should not emit a
- // btrfsitem.RootRef for other item types without this code also being
- // updated.
- panic(fmt.Errorf("should not happen: RootRef: unexpected ItemType=%v", item.Key.ItemType))
- }
- // sibling
- o.wantOff(ctx, fmt.Sprintf("corresponding %v", otherType),
- treeID,
- btrfsprim.ObjID(item.Key.Offset),
- otherType,
- uint64(item.Key.ObjectID))
- // parent
- o.want(ctx, "parent subvolume: Root",
- treeID,
- parent,
- btrfsitem.ROOT_ITEM_KEY)
- o.wantOff(ctx, "parent subvolume: Inode of parent dir",
- parent,
- body.DirID,
- btrfsitem.INODE_ITEM_KEY,
- 0)
- o.wantOff(ctx, "parent subvolume: DIR_ITEM in parent dir",
- parent,
- body.DirID,
- btrfsitem.DIR_ITEM_KEY,
- btrfsitem.NameHash(body.Name))
- o.wantOff(ctx, "parent subvolume: DIR_INDEX in parent dir",
- parent,
- body.DirID,
- btrfsitem.DIR_INDEX_KEY,
- uint64(body.Sequence))
- // child
- o.want(ctx, "child subvolume: Root",
- treeID,
- child,
- btrfsitem.ROOT_ITEM_KEY)
- case *btrfsitem.SharedDataRef:
- o.want(ctx, "Extent",
- btrfsprim.EXTENT_TREE_OBJECTID,
- item.Key.ObjectID,
- btrfsitem.EXTENT_ITEM_KEY)
- case *btrfsitem.UUIDMap:
- o.want(ctx, "subvolume Root",
- btrfsprim.ROOT_TREE_OBJECTID,
- body.ObjID,
- btrfsitem.ROOT_ITEM_KEY)
- case *btrfsitem.Error:
- o.fsErr(ctx, fmt.Errorf("error decoding item: %w", body.Err))
- default:
- // This is a panic because the item decoder should not emit new types without this
- // code also being updated.
- panic(fmt.Errorf("should not happen: unexpected item type: %T", body))
- }
-}
diff --git a/lib/btrfsprogs/btrfsinspect/rebuildnodes/rebuild_treecb.go b/lib/btrfsprogs/btrfsinspect/rebuildnodes/rebuild_treecb.go
deleted file mode 100644
index 492436b..0000000
--- a/lib/btrfsprogs/btrfsinspect/rebuildnodes/rebuild_treecb.go
+++ /dev/null
@@ -1,86 +0,0 @@
-// Copyright (C) 2022-2023 Luke Shumaker <lukeshu@lukeshu.com>
-//
-// SPDX-License-Identifier: GPL-2.0-or-later
-
-package rebuildnodes
-
-import (
- "context"
- "fmt"
-
- "git.lukeshu.com/btrfs-progs-ng/lib/btrfs/btrfsitem"
- "git.lukeshu.com/btrfs-progs-ng/lib/btrfs/btrfsprim"
- "git.lukeshu.com/btrfs-progs-ng/lib/btrfs/btrfsvol"
-)
-
-// AddedItem implements btrees.Callbacks.
-func (o *rebuilder) AddedItem(ctx context.Context, tree btrfsprim.ObjID, key btrfsprim.Key) {
- o.addedItemQueue.Insert(keyAndTree{
- TreeID: tree,
- Key: key,
- })
-}
-
-// AddedRoot implements btrees.Callbacks.
-func (o *rebuilder) AddedRoot(ctx context.Context, tree btrfsprim.ObjID, root btrfsvol.LogicalAddr) {
- if retries := o.retryItemQueue[tree]; retries != nil {
- o.addedItemQueue.InsertFrom(retries)
- }
-}
-
-// LookupRoot implements btrees.Callbacks.
-func (o *rebuilder) LookupRoot(ctx context.Context, tree btrfsprim.ObjID) (offset btrfsprim.Generation, item btrfsitem.Root, ok bool) {
- wantKey := WantWithTree{
- TreeID: btrfsprim.ROOT_TREE_OBJECTID,
- Key: Want{
- ObjectID: tree,
- ItemType: btrfsitem.ROOT_ITEM_KEY,
- OffsetType: offsetAny,
- },
- }
- ctx = withWant(ctx, logFieldTreeWant, "tree Root", wantKey)
- foundKey, ok := o._want(ctx, wantKey)
- if !ok {
- o.enqueueRetry(btrfsprim.ROOT_TREE_OBJECTID)
- return 0, btrfsitem.Root{}, false
- }
- itemBody := o.rebuilt.Tree(ctx, wantKey.TreeID).ReadItem(ctx, foundKey)
- defer itemBody.Free()
- switch itemBody := itemBody.(type) {
- case *btrfsitem.Root:
- return btrfsprim.Generation(foundKey.Offset), *itemBody, true
- case *btrfsitem.Error:
- o.fsErr(ctx, fmt.Errorf("error decoding item: %v: %w", foundKey, itemBody.Err))
- return 0, btrfsitem.Root{}, false
- default:
- // This is a panic because the item decoder should not emit ROOT_ITEM items as anything but
- // btrfsitem.Root or btrfsitem.Error without this code also being updated.
- panic(fmt.Errorf("should not happen: ROOT_ITEM item has unexpected type: %T", itemBody))
- }
-}
-
-// LookupUUID implements btrees.Callbacks.
-func (o *rebuilder) LookupUUID(ctx context.Context, uuid btrfsprim.UUID) (id btrfsprim.ObjID, ok bool) {
- wantKey := WantWithTree{
- TreeID: btrfsprim.UUID_TREE_OBJECTID,
- Key: wantFromKey(btrfsitem.UUIDToKey(uuid)),
- }
- ctx = withWant(ctx, logFieldTreeWant, "resolve parent UUID", wantKey)
- if !o._wantOff(ctx, wantKey) {
- o.enqueueRetry(btrfsprim.UUID_TREE_OBJECTID)
- return 0, false
- }
- itemBody := o.rebuilt.Tree(ctx, wantKey.TreeID).ReadItem(ctx, wantKey.Key.Key())
- defer itemBody.Free()
- switch itemBody := itemBody.(type) {
- case *btrfsitem.UUIDMap:
- return itemBody.ObjID, true
- case *btrfsitem.Error:
- o.fsErr(ctx, fmt.Errorf("error decoding item: %v: %w", wantKey, itemBody.Err))
- return 0, false
- default:
- // This is a panic because the item decoder should not emit UUID_SUBVOL items as anything but
- // btrfsitem.UUIDMap or btrfsitem.Error without this code also being updated.
- panic(fmt.Errorf("should not happen: UUID_SUBVOL item has unexpected type: %T", itemBody))
- }
-}
diff --git a/lib/btrfsprogs/btrfsinspect/rebuildnodes/rebuild_wantcb.go b/lib/btrfsprogs/btrfsinspect/rebuildnodes/rebuild_wantcb.go
deleted file mode 100644
index adf3cff..0000000
--- a/lib/btrfsprogs/btrfsinspect/rebuildnodes/rebuild_wantcb.go
+++ /dev/null
@@ -1,400 +0,0 @@
-// Copyright (C) 2022-2023 Luke Shumaker <lukeshu@lukeshu.com>
-//
-// SPDX-License-Identifier: GPL-2.0-or-later
-
-package rebuildnodes
-
-import (
- "bytes"
- "context"
- "fmt"
-
- "github.com/datawire/dlib/dlog"
-
- "git.lukeshu.com/btrfs-progs-ng/lib/btrfs/btrfsitem"
- "git.lukeshu.com/btrfs-progs-ng/lib/btrfs/btrfsprim"
- "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/btrfsprogs/btrfsinspect/rebuildnodes/keyio"
- "git.lukeshu.com/btrfs-progs-ng/lib/containers"
-)
-
-// fsErr implements rebuildCallbacks.
-func (o *rebuilder) fsErr(ctx context.Context, e error) {
- dlog.Errorf(ctx, "filesystem error: %v", e)
-}
-
-// want implements rebuildCallbacks.
-func (o *rebuilder) want(ctx context.Context, reason string, treeID btrfsprim.ObjID, objID btrfsprim.ObjID, typ btrfsprim.ItemType) {
- wantKey := WantWithTree{
- TreeID: treeID,
- Key: Want{
- ObjectID: objID,
- ItemType: typ,
- OffsetType: offsetAny,
- },
- }
- ctx = withWant(ctx, logFieldItemWant, reason, wantKey)
- o._want(ctx, wantKey)
-}
-
-func (o *rebuilder) _want(ctx context.Context, wantKey WantWithTree) (key btrfsprim.Key, ok bool) {
- if o.rebuilt.Tree(ctx, wantKey.TreeID) == nil {
- o.enqueueRetry(wantKey.TreeID)
- return btrfsprim.Key{}, false
- }
-
- // check if we already have it
-
- tgt := wantKey.Key.Key()
- if key, _, ok := o.rebuilt.Tree(ctx, wantKey.TreeID).Items(ctx).Search(func(key btrfsprim.Key, _ keyio.ItemPtr) int {
- key.Offset = 0
- return tgt.Compare(key)
- }); ok {
- return key, true
- }
-
- // OK, we need to insert it
-
- if o.hasAugment(wantKey) {
- return btrfsprim.Key{}, false
- }
- wants := make(containers.Set[btrfsvol.LogicalAddr])
- o.rebuilt.Tree(ctx, wantKey.TreeID).PotentialItems(ctx).Subrange(
- func(k btrfsprim.Key, _ keyio.ItemPtr) int {
- k.Offset = 0
- return tgt.Compare(k)
- },
- func(_ btrfsprim.Key, v keyio.ItemPtr) bool {
- wants.InsertFrom(o.rebuilt.Tree(ctx, wantKey.TreeID).LeafToRoots(ctx, v.Node))
- return true
- })
- o.wantAugment(ctx, wantKey, wants)
- return btrfsprim.Key{}, false
-}
-
-// wantOff implements rebuildCallbacks.
-func (o *rebuilder) wantOff(ctx context.Context, reason string, treeID btrfsprim.ObjID, objID btrfsprim.ObjID, typ btrfsprim.ItemType, off uint64) {
- wantKey := WantWithTree{
- TreeID: treeID,
- Key: Want{
- ObjectID: objID,
- ItemType: typ,
- OffsetType: offsetExact,
- OffsetLow: off,
- },
- }
- ctx = withWant(ctx, logFieldItemWant, reason, wantKey)
- o._wantOff(ctx, wantKey)
-}
-
-func (o *rebuilder) _wantOff(ctx context.Context, wantKey WantWithTree) (ok bool) {
- if o.rebuilt.Tree(ctx, wantKey.TreeID) == nil {
- o.enqueueRetry(wantKey.TreeID)
- return false
- }
-
- // check if we already have it
-
- tgt := wantKey.Key.Key()
- if _, ok := o.rebuilt.Tree(ctx, wantKey.TreeID).Items(ctx).Load(tgt); ok {
- return true
- }
-
- // OK, we need to insert it
-
- if o.hasAugment(wantKey) {
- return false
- }
- wants := make(containers.Set[btrfsvol.LogicalAddr])
- o.rebuilt.Tree(ctx, wantKey.TreeID).PotentialItems(ctx).Subrange(
- func(k btrfsprim.Key, _ keyio.ItemPtr) int { return tgt.Compare(k) },
- func(_ btrfsprim.Key, v keyio.ItemPtr) bool {
- wants.InsertFrom(o.rebuilt.Tree(ctx, wantKey.TreeID).LeafToRoots(ctx, v.Node))
- return true
- })
- o.wantAugment(ctx, wantKey, wants)
- return false
-}
-
-// wantDirIndex implements rebuildCallbacks.
-func (o *rebuilder) wantDirIndex(ctx context.Context, reason string, treeID btrfsprim.ObjID, objID btrfsprim.ObjID, name []byte) {
- wantKey := WantWithTree{
- TreeID: treeID,
- Key: Want{
- ObjectID: objID,
- ItemType: btrfsitem.DIR_INDEX_KEY,
- OffsetType: offsetName,
- OffsetName: string(name),
- },
- }
- ctx = withWant(ctx, logFieldItemWant, reason, wantKey)
-
- if o.rebuilt.Tree(ctx, treeID) == nil {
- o.enqueueRetry(treeID)
- return
- }
-
- // check if we already have it
-
- tgt := wantKey.Key.Key()
- found := false
- o.rebuilt.Tree(ctx, treeID).Items(ctx).Subrange(
- func(key btrfsprim.Key, _ keyio.ItemPtr) int {
- key.Offset = 0
- return tgt.Compare(key)
- },
- func(_ btrfsprim.Key, ptr keyio.ItemPtr) bool {
- if itemName, ok := o.keyIO.Names[ptr]; ok && bytes.Equal(itemName, name) {
- found = true
- }
- return !found
- })
- if found {
- return
- }
-
- // OK, we need to insert it
-
- if o.hasAugment(wantKey) {
- return
- }
- wants := make(containers.Set[btrfsvol.LogicalAddr])
- o.rebuilt.Tree(ctx, treeID).PotentialItems(ctx).Subrange(
- func(key btrfsprim.Key, _ keyio.ItemPtr) int {
- key.Offset = 0
- return tgt.Compare(key)
- },
- func(_ btrfsprim.Key, ptr keyio.ItemPtr) bool {
- if itemName, ok := o.keyIO.Names[ptr]; ok && bytes.Equal(itemName, name) {
- wants.InsertFrom(o.rebuilt.Tree(ctx, treeID).LeafToRoots(ctx, ptr.Node))
- }
- return true
- })
- o.wantAugment(ctx, wantKey, wants)
-}
-
-func (o *rebuilder) _walkRange(
- ctx context.Context,
- items *containers.SortedMap[btrfsprim.Key, keyio.ItemPtr],
- treeID, objID btrfsprim.ObjID, typ btrfsprim.ItemType,
- beg, end uint64,
- fn func(key btrfsprim.Key, ptr keyio.ItemPtr, beg, end uint64),
-) {
- min := btrfsprim.Key{
- ObjectID: objID,
- ItemType: typ,
- Offset: 0, // *NOT* `beg`
- }
- max := btrfsprim.Key{
- ObjectID: objID,
- ItemType: typ,
- Offset: end - 1,
- }
- items.Subrange(
- func(runKey btrfsprim.Key, _ keyio.ItemPtr) int {
- switch {
- case min.Compare(runKey) < 0:
- return 1
- case max.Compare(runKey) > 0:
- return -1
- default:
- return 0
- }
- },
- func(runKey btrfsprim.Key, runPtr keyio.ItemPtr) bool {
- runSizeAndErr, ok := o.keyIO.Sizes[runPtr]
- if !ok {
- panic(fmt.Errorf("should not happen: %v (%v) did not have a size recorded",
- runPtr, keyAndTree{TreeID: treeID, Key: runKey}))
- }
- if runSizeAndErr.Err != nil {
- o.fsErr(ctx, fmt.Errorf("get size: %v (%v): %w",
- runPtr, keyAndTree{TreeID: treeID, Key: runKey},
- runSizeAndErr.Err))
- return true
- }
- runSize := runSizeAndErr.Size
- if runSize == 0 {
- return true
- }
- runBeg := runKey.Offset
- runEnd := runBeg + runSize
- if runEnd <= beg {
- return true
- }
-
- fn(runKey, runPtr, runBeg, runEnd)
- return true
- })
-}
-
-type gap struct {
- // range is [Beg,End)
- Beg, End uint64
-}
-
-// Compare implements containers.Ordered.
-func (a gap) Compare(b gap) int {
- return containers.NativeCompare(a.Beg, b.Beg)
-}
-
-func (o *rebuilder) _wantRange(
- ctx context.Context, reason string,
- treeID btrfsprim.ObjID, objID btrfsprim.ObjID, typ btrfsprim.ItemType,
- beg, end uint64,
-) {
- wantKey := WantWithTree{
- TreeID: treeID,
- Key: Want{
- ObjectID: objID,
- ItemType: typ,
- OffsetType: offsetAny,
- },
- }
- ctx = withWant(ctx, logFieldItemWant, reason, wantKey)
- wantKey.Key.OffsetType = offsetRange
-
- if o.rebuilt.Tree(ctx, treeID) == nil {
- o.enqueueRetry(treeID)
- return
- }
-
- // Step 1: Build a listing of the gaps.
- //
- // Start with a gap of the whole range, then subtract each run
- // from it.
- gaps := new(containers.RBTree[gap])
- gaps.Insert(gap{
- Beg: beg,
- End: end,
- })
- o._walkRange(
- ctx,
- o.rebuilt.Tree(ctx, treeID).Items(ctx),
- treeID, objID, typ, beg, end,
- func(runKey btrfsprim.Key, _ keyio.ItemPtr, runBeg, runEnd uint64) {
- var overlappingGaps []*containers.RBNode[gap]
- gaps.Subrange(
- func(gap gap) int {
- switch {
- case gap.End <= runBeg:
- return 1
- case runEnd <= gap.Beg:
- return -1
- default:
- return 0
- }
- },
- func(node *containers.RBNode[gap]) bool {
- overlappingGaps = append(overlappingGaps, node)
- return true
- })
- if len(overlappingGaps) == 0 {
- return
- }
- gapsBeg := overlappingGaps[0].Value.Beg
- gapsEnd := overlappingGaps[len(overlappingGaps)-1].Value.End
- for _, gap := range overlappingGaps {
- gaps.Delete(gap)
- }
- if gapsBeg < runBeg {
- gaps.Insert(gap{
- Beg: gapsBeg,
- End: runBeg,
- })
- }
- if gapsEnd > runEnd {
- gaps.Insert(gap{
- Beg: runEnd,
- End: gapsEnd,
- })
- }
- })
-
- // Step 2: Fill each gap.
- if gaps.Len() == 0 {
- return
- }
- potentialItems := o.rebuilt.Tree(ctx, treeID).PotentialItems(ctx)
- gaps.Range(func(rbNode *containers.RBNode[gap]) bool {
- gap := rbNode.Value
- last := gap.Beg
- o._walkRange(
- ctx,
- potentialItems,
- treeID, objID, typ, gap.Beg, gap.End,
- func(k btrfsprim.Key, v keyio.ItemPtr, runBeg, runEnd uint64) {
- // TODO: This is dumb and greedy.
- if last < runBeg {
- // log an error
- wantKey.Key.OffsetLow = last
- wantKey.Key.OffsetHigh = runBeg
- wantCtx := withWant(ctx, logFieldItemWant, reason, wantKey)
- o.wantAugment(wantCtx, wantKey, nil)
- }
- wantKey.Key.OffsetLow = gap.Beg
- wantKey.Key.OffsetHigh = gap.End
- wantCtx := withWant(ctx, logFieldItemWant, reason, wantKey)
- o.wantAugment(wantCtx, wantKey, o.rebuilt.Tree(wantCtx, treeID).LeafToRoots(wantCtx, v.Node))
- last = runEnd
- })
- if last < gap.End {
- // log an error
- wantKey.Key.OffsetLow = last
- wantKey.Key.OffsetHigh = gap.End
- wantCtx := withWant(ctx, logFieldItemWant, reason, wantKey)
- o.wantAugment(wantCtx, wantKey, nil)
- }
- return true
- })
-}
-
-// func implements rebuildCallbacks.
-//
-// interval is [beg, end)
-func (o *rebuilder) wantCSum(ctx context.Context, reason string, inodeTree, inode btrfsprim.ObjID, beg, end btrfsvol.LogicalAddr) {
- inodeWant := WantWithTree{
- TreeID: inodeTree,
- Key: Want{
- ObjectID: inode,
- ItemType: btrfsitem.INODE_ITEM_KEY,
- OffsetType: offsetExact,
- OffsetLow: 0,
- },
- }
- inodeCtx := withWant(ctx, logFieldItemWant, reason, inodeWant)
- if !o._wantOff(inodeCtx, inodeWant) {
- o.enqueueRetry(inodeTree)
- return
- }
- inodePtr, ok := o.rebuilt.Tree(inodeCtx, inodeTree).Items(inodeCtx).Load(inodeWant.Key.Key())
- if !ok {
- panic(fmt.Errorf("should not happen: could not load key: %v", inodeWant))
- }
- inodeFlags, ok := o.keyIO.Flags[inodePtr]
- if !ok {
- panic(fmt.Errorf("should not happen: INODE_ITEM did not have flags recorded"))
- }
- if inodeFlags.Err != nil {
- o.fsErr(inodeCtx, inodeFlags.Err)
- return
- }
-
- if inodeFlags.NoDataSum {
- return
- }
-
- o._wantRange(
- ctx, reason,
- btrfsprim.CSUM_TREE_OBJECTID, btrfsprim.EXTENT_CSUM_OBJECTID, btrfsprim.EXTENT_CSUM_KEY,
- uint64(roundDown(beg, btrfssum.BlockSize)), uint64(roundUp(end, btrfssum.BlockSize)))
-}
-
-// wantFileExt implements rebuildCallbacks.
-func (o *rebuilder) wantFileExt(ctx context.Context, reason string, treeID btrfsprim.ObjID, ino btrfsprim.ObjID, size int64) {
- o._wantRange(
- ctx, reason,
- treeID, ino, btrfsprim.EXTENT_DATA_KEY,
- 0, uint64(size))
-}
diff --git a/lib/btrfsprogs/btrfsinspect/rebuildnodes/rebuild_wanttyp.go b/lib/btrfsprogs/btrfsinspect/rebuildnodes/rebuild_wanttyp.go
deleted file mode 100644
index 2b471fe..0000000
--- a/lib/btrfsprogs/btrfsinspect/rebuildnodes/rebuild_wanttyp.go
+++ /dev/null
@@ -1,107 +0,0 @@
-// Copyright (C) 2022-2023 Luke Shumaker <lukeshu@lukeshu.com>
-//
-// SPDX-License-Identifier: GPL-2.0-or-later
-
-package rebuildnodes
-
-import (
- "context"
- "fmt"
-
- "github.com/datawire/dlib/dlog"
-
- "git.lukeshu.com/btrfs-progs-ng/lib/btrfs/btrfsprim"
- "git.lukeshu.com/btrfs-progs-ng/lib/containers"
-)
-
-type wantOffsetType int8
-
-const (
- offsetAny = wantOffsetType(iota)
- offsetExact
- offsetRange
- offsetName
-)
-
-type Want struct {
- ObjectID btrfsprim.ObjID
- ItemType btrfsprim.ItemType
- OffsetType wantOffsetType
- OffsetLow uint64
- OffsetHigh uint64
- OffsetName string
-}
-
-func (a Want) Compare(b Want) int {
- if d := containers.NativeCompare(a.ObjectID, b.ObjectID); d != 0 {
- return d
- }
- if d := containers.NativeCompare(a.ItemType, b.ItemType); d != 0 {
- return d
- }
- if d := containers.NativeCompare(a.OffsetType, b.OffsetType); d != 0 {
- return d
- }
- if d := containers.NativeCompare(a.OffsetLow, b.OffsetLow); d != 0 {
- return d
- }
- if d := containers.NativeCompare(a.OffsetHigh, b.OffsetHigh); d != 0 {
- return d
- }
- if d := containers.NativeCompare(a.OffsetName, b.OffsetName); d != 0 {
- return d
- }
- return 0
-}
-
-func (o Want) Key() btrfsprim.Key {
- return btrfsprim.Key{
- ObjectID: o.ObjectID,
- ItemType: o.ItemType,
- Offset: o.OffsetLow,
- }
-}
-
-func wantFromKey(k btrfsprim.Key) Want {
- return Want{
- ObjectID: k.ObjectID,
- ItemType: k.ItemType,
- OffsetType: offsetExact,
- OffsetLow: k.Offset,
- }
-}
-
-func (o Want) String() string {
- switch o.OffsetType {
- case offsetAny:
- return fmt.Sprintf("{%v %v ?}", o.ObjectID, o.ItemType)
- case offsetExact:
- return fmt.Sprintf("{%v %v %v}", o.ObjectID, o.ItemType, o.OffsetLow)
- case offsetRange:
- return fmt.Sprintf("{%v %v %v-%v}", o.ObjectID, o.ItemType, o.OffsetLow, o.OffsetHigh)
- case offsetName:
- return fmt.Sprintf("{%v %v name=%q}", o.ObjectID, o.ItemType, o.OffsetName)
- default:
- panic(fmt.Errorf("should not happen: OffsetType=%#v", o.OffsetType))
- }
-}
-
-type WantWithTree struct {
- TreeID btrfsprim.ObjID
- Key Want
-}
-
-func (o WantWithTree) String() string {
- return fmt.Sprintf("tree=%v key=%v", o.TreeID, o.Key)
-}
-
-const (
- logFieldItemWant = "btrfsinspect.rebuild-nodes.rebuild.want"
- logFieldTreeWant = "btrfsinspect.rebuild-nodes.rebuild.add-tree.want"
-)
-
-func withWant(ctx context.Context, logField, reason string, wantKey WantWithTree) context.Context {
- ctx = dlog.WithField(ctx, logField+".reason", reason)
- ctx = dlog.WithField(ctx, logField+".key", wantKey)
- return ctx
-}
diff --git a/lib/btrfsprogs/btrfsinspect/rebuildnodes/scan.go b/lib/btrfsprogs/btrfsinspect/rebuildnodes/scan.go
deleted file mode 100644
index 17949ab..0000000
--- a/lib/btrfsprogs/btrfsinspect/rebuildnodes/scan.go
+++ /dev/null
@@ -1,77 +0,0 @@
-// Copyright (C) 2022-2023 Luke Shumaker <lukeshu@lukeshu.com>
-//
-// SPDX-License-Identifier: GPL-2.0-or-later
-
-package rebuildnodes
-
-import (
- "context"
- "time"
-
- "github.com/datawire/dlib/dlog"
-
- "git.lukeshu.com/btrfs-progs-ng/lib/btrfs"
- "git.lukeshu.com/btrfs-progs-ng/lib/btrfs/btrfstree"
- "git.lukeshu.com/btrfs-progs-ng/lib/btrfs/btrfsvol"
- "git.lukeshu.com/btrfs-progs-ng/lib/btrfsprogs/btrfsinspect"
- "git.lukeshu.com/btrfs-progs-ng/lib/btrfsprogs/btrfsinspect/rebuildnodes/graph"
- "git.lukeshu.com/btrfs-progs-ng/lib/btrfsprogs/btrfsinspect/rebuildnodes/keyio"
- "git.lukeshu.com/btrfs-progs-ng/lib/containers"
- "git.lukeshu.com/btrfs-progs-ng/lib/maps"
- "git.lukeshu.com/btrfs-progs-ng/lib/textui"
-)
-
-func ScanDevices(ctx context.Context, fs *btrfs.FS, scanResults btrfsinspect.ScanDevicesResult) (btrfstree.Superblock, graph.Graph, *keyio.Handle, error) {
- dlog.Info(ctx, "Reading superblock...")
- sb, err := fs.Superblock()
- if err != nil {
- return btrfstree.Superblock{}, graph.Graph{}, nil, err
- }
-
- dlog.Infof(ctx, "Reading node data from FS...")
-
- var stats textui.Portion[int]
- stats.D = countNodes(scanResults)
- progressWriter := textui.NewProgress[textui.Portion[int]](
- dlog.WithField(ctx, "btrfsinspect.rebuild-nodes.read.substep", "read-nodes"),
- dlog.LogLevelInfo, textui.Tunable(1*time.Second))
-
- nodeGraph := graph.New(*sb)
- keyIO := keyio.NewHandle(fs, *sb)
-
- progressWriter.Set(stats)
- for _, devResults := range scanResults {
- for _, laddr := range maps.SortedKeys(devResults.FoundNodes) {
- if err := ctx.Err(); err != nil {
- return btrfstree.Superblock{}, graph.Graph{}, nil, err
- }
- nodeRef, err := btrfstree.ReadNode[btrfsvol.LogicalAddr](fs, *sb, laddr, btrfstree.NodeExpectations{
- LAddr: containers.Optional[btrfsvol.LogicalAddr]{OK: true, Val: laddr},
- })
- if err != nil {
- btrfstree.FreeNodeRef(nodeRef)
- return btrfstree.Superblock{}, graph.Graph{}, nil, err
- }
-
- nodeGraph.InsertNode(nodeRef)
- keyIO.InsertNode(nodeRef)
-
- btrfstree.FreeNodeRef(nodeRef)
-
- stats.N++
- progressWriter.Set(stats)
- }
- }
- if stats.N != stats.D {
- panic("should not happen")
- }
- progressWriter.Done()
- dlog.Info(ctx, "... done reading node data")
-
- if err := nodeGraph.FinalCheck(ctx, fs, *sb); err != nil {
- return btrfstree.Superblock{}, graph.Graph{}, nil, err
- }
- keyIO.SetGraph(*nodeGraph)
-
- return *sb, *nodeGraph, keyIO, nil
-}
diff --git a/lib/btrfsprogs/btrfsinspect/rebuildnodes/util.go b/lib/btrfsprogs/btrfsinspect/rebuildnodes/util.go
deleted file mode 100644
index 9d91f23..0000000
--- a/lib/btrfsprogs/btrfsinspect/rebuildnodes/util.go
+++ /dev/null
@@ -1,31 +0,0 @@
-// Copyright (C) 2022 Luke Shumaker <lukeshu@lukeshu.com>
-//
-// SPDX-License-Identifier: GPL-2.0-or-later
-
-package rebuildnodes
-
-import (
- "golang.org/x/exp/constraints"
-
- "git.lukeshu.com/btrfs-progs-ng/lib/btrfsprogs/btrfsinspect"
-)
-
-func countNodes(nodeScanResults btrfsinspect.ScanDevicesResult) int {
- var cnt int
- for _, devResults := range nodeScanResults {
- cnt += len(devResults.FoundNodes)
- }
- return cnt
-}
-
-func roundDown[T constraints.Integer](n, d T) T {
- return (n / d) * d
-}
-
-func roundUp[T constraints.Integer](n, d T) T {
- return ((n + d - 1) / d) * d
-}
-
-func discardOK[T any](val T, _ bool) T {
- return val
-}
diff --git a/lib/btrfsprogs/btrfsinspect/scandevices.go b/lib/btrfsprogs/btrfsinspect/scandevices.go
deleted file mode 100644
index d54be71..0000000
--- a/lib/btrfsprogs/btrfsinspect/scandevices.go
+++ /dev/null
@@ -1,260 +0,0 @@
-// Copyright (C) 2022-2023 Luke Shumaker <lukeshu@lukeshu.com>
-//
-// SPDX-License-Identifier: GPL-2.0-or-later
-
-package btrfsinspect
-
-import (
- "context"
- "errors"
- "fmt"
- "strings"
- "sync"
- "time"
-
- "github.com/datawire/dlib/dgroup"
- "github.com/datawire/dlib/dlog"
-
- "git.lukeshu.com/btrfs-progs-ng/lib/binstruct"
- "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/btrfsprim"
- "git.lukeshu.com/btrfs-progs-ng/lib/btrfs/btrfssum"
- "git.lukeshu.com/btrfs-progs-ng/lib/btrfs/btrfstree"
- "git.lukeshu.com/btrfs-progs-ng/lib/btrfs/btrfsvol"
- "git.lukeshu.com/btrfs-progs-ng/lib/containers"
- "git.lukeshu.com/btrfs-progs-ng/lib/textui"
-)
-
-type ScanDevicesResult map[btrfsvol.DeviceID]ScanOneDeviceResult
-
-func ScanDevices(ctx context.Context, fs *btrfs.FS) (ScanDevicesResult, error) {
- grp := dgroup.NewGroup(ctx, dgroup.GroupConfig{})
- var mu sync.Mutex
- result := make(map[btrfsvol.DeviceID]ScanOneDeviceResult)
- for id, dev := range fs.LV.PhysicalVolumes() {
- id := id
- dev := dev
- grp.Go(fmt.Sprintf("dev-%d", id), func(ctx context.Context) error {
- sb, err := dev.Superblock()
- if err != nil {
- return err
- }
- devResult, err := ScanOneDevice(ctx, dev, *sb)
- if err != nil {
- return err
- }
- mu.Lock()
- result[id] = devResult
- mu.Unlock()
- return nil
- })
- }
- if err := grp.Wait(); err != nil {
- return nil, err
- }
- return result, nil
-}
-
-type ScanOneDeviceResult struct {
- Checksums btrfssum.SumRun[btrfsvol.PhysicalAddr]
- FoundNodes map[btrfsvol.LogicalAddr][]btrfsvol.PhysicalAddr
- FoundChunks []btrfstree.SysChunk
- FoundBlockGroups []SysBlockGroup
- FoundDevExtents []SysDevExtent
- FoundExtentCSums []SysExtentCSum
-}
-
-type SysBlockGroup struct {
- Key btrfsprim.Key
- BG btrfsitem.BlockGroup
-}
-
-type SysDevExtent struct {
- Key btrfsprim.Key
- DevExt btrfsitem.DevExtent
-}
-
-type SysExtentCSum struct {
- Generation btrfsprim.Generation
- Sums btrfsitem.ExtentCSum
-}
-
-// Compare implements containers.Ordered.
-func (a SysExtentCSum) Compare(b SysExtentCSum) int {
- return containers.NativeCompare(a.Sums.Addr, b.Sums.Addr)
-}
-
-type scanStats struct {
- textui.Portion[btrfsvol.PhysicalAddr]
-
- NumFoundNodes int
- NumFoundChunks int
- NumFoundBlockGroups int
- NumFoundDevExtents int
- NumFoundExtentCSums int
-}
-
-func (s scanStats) String() string {
- return textui.Sprintf("scanned %v (found: %v nodes, %v chunks, %v block groups, %v dev extents, %v sum items)",
- s.Portion,
- s.NumFoundNodes,
- s.NumFoundChunks,
- s.NumFoundBlockGroups,
- s.NumFoundDevExtents,
- s.NumFoundExtentCSums)
-}
-
-var sbSize = btrfsvol.PhysicalAddr(binstruct.StaticSize(btrfstree.Superblock{}))
-
-// ScanOneDevice mostly mimics btrfs-progs
-// cmds/rescue-chunk-recover.c:scan_one_device().
-func ScanOneDevice(ctx context.Context, dev *btrfs.Device, sb btrfstree.Superblock) (ScanOneDeviceResult, error) {
- ctx = dlog.WithField(ctx, "btrfsinspect.scandevices.dev", dev.Name())
-
- result := ScanOneDeviceResult{
- FoundNodes: make(map[btrfsvol.LogicalAddr][]btrfsvol.PhysicalAddr),
- }
-
- devSize := dev.Size()
- if sb.NodeSize < sb.SectorSize {
- return result, fmt.Errorf("node_size(%v) < sector_size(%v)",
- sb.NodeSize, sb.SectorSize)
- }
- if sb.SectorSize != btrfssum.BlockSize {
- // TODO: probably handle this?
- return result, fmt.Errorf("sector_size(%v) != btrfssum.BlockSize",
- sb.SectorSize)
- }
- alg := sb.ChecksumType
- csumSize := alg.Size()
- numSums := int(devSize / btrfssum.BlockSize)
- var sums strings.Builder
- sums.Grow(numSums * csumSize)
-
- progressWriter := textui.NewProgress[scanStats](ctx, dlog.LogLevelInfo, textui.Tunable(1*time.Second))
- progress := func(pos btrfsvol.PhysicalAddr) {
- progressWriter.Set(scanStats{
- Portion: textui.Portion[btrfsvol.PhysicalAddr]{
- N: pos,
- D: devSize,
- },
- NumFoundNodes: len(result.FoundNodes),
- NumFoundChunks: len(result.FoundChunks),
- NumFoundBlockGroups: len(result.FoundBlockGroups),
- NumFoundDevExtents: len(result.FoundDevExtents),
- NumFoundExtentCSums: len(result.FoundExtentCSums),
- })
- }
-
- var minNextNode btrfsvol.PhysicalAddr
- for i := 0; i < numSums; i++ {
- if ctx.Err() != nil {
- return result, ctx.Err()
- }
- pos := btrfsvol.PhysicalAddr(i * btrfssum.BlockSize)
- progress(pos)
-
- sum, err := btrfs.ChecksumPhysical(dev, alg, pos)
- if err != nil {
- return result, err
- }
- sums.Write(sum[:csumSize])
-
- checkForNode := pos >= minNextNode && pos+btrfsvol.PhysicalAddr(sb.NodeSize) <= devSize
- if checkForNode {
- for _, sbAddr := range btrfs.SuperblockAddrs {
- if sbAddr <= pos && pos < sbAddr+sbSize {
- checkForNode = false
- break
- }
- }
- }
-
- if checkForNode {
- nodeRef, err := btrfstree.ReadNode[btrfsvol.PhysicalAddr](dev, sb, pos, btrfstree.NodeExpectations{})
- if err != nil {
- if !errors.Is(err, btrfstree.ErrNotANode) {
- dlog.Errorf(ctx, "error: %v", err)
- }
- } else {
- result.FoundNodes[nodeRef.Data.Head.Addr] = append(result.FoundNodes[nodeRef.Data.Head.Addr], nodeRef.Addr)
- for i, item := range nodeRef.Data.BodyLeaf {
- switch item.Key.ItemType {
- case btrfsitem.CHUNK_ITEM_KEY:
- switch itemBody := item.Body.(type) {
- case *btrfsitem.Chunk:
- dlog.Tracef(ctx, "node@%v: item %v: found chunk",
- nodeRef.Addr, i)
- result.FoundChunks = append(result.FoundChunks, btrfstree.SysChunk{
- Key: item.Key,
- Chunk: *itemBody,
- })
- case *btrfsitem.Error:
- dlog.Errorf(ctx, "node@%v: item %v: error: malformed CHUNK_ITEM: %v",
- nodeRef.Addr, i, itemBody.Err)
- default:
- panic(fmt.Errorf("should not happen: CHUNK_ITEM has unexpected item type: %T", itemBody))
- }
- case btrfsitem.BLOCK_GROUP_ITEM_KEY:
- switch itemBody := item.Body.(type) {
- case *btrfsitem.BlockGroup:
- dlog.Tracef(ctx, "node@%v: item %v: found block group",
- nodeRef.Addr, i)
- result.FoundBlockGroups = append(result.FoundBlockGroups, SysBlockGroup{
- Key: item.Key,
- BG: *itemBody,
- })
- case *btrfsitem.Error:
- dlog.Errorf(ctx, "node@%v: item %v: error: malformed BLOCK_GROUP_ITEM: %v",
- nodeRef.Addr, i, itemBody.Err)
- default:
- panic(fmt.Errorf("should not happen: BLOCK_GROUP_ITEM has unexpected item type: %T", itemBody))
- }
- case btrfsitem.DEV_EXTENT_KEY:
- switch itemBody := item.Body.(type) {
- case *btrfsitem.DevExtent:
- dlog.Tracef(ctx, "node@%v: item %v: found dev extent",
- nodeRef.Addr, i)
- result.FoundDevExtents = append(result.FoundDevExtents, SysDevExtent{
- Key: item.Key,
- DevExt: *itemBody,
- })
- case *btrfsitem.Error:
- dlog.Errorf(ctx, "node@%v: item %v: error: malformed DEV_EXTENT: %v",
- nodeRef.Addr, i, itemBody.Err)
- default:
- panic(fmt.Errorf("should not happen: DEV_EXTENT has unexpected item type: %T", itemBody))
- }
- case btrfsitem.EXTENT_CSUM_KEY:
- switch itemBody := item.Body.(type) {
- case *btrfsitem.ExtentCSum:
- dlog.Tracef(ctx, "node@%v: item %v: found csums",
- nodeRef.Addr, i)
- result.FoundExtentCSums = append(result.FoundExtentCSums, SysExtentCSum{
- Generation: nodeRef.Data.Head.Generation,
- Sums: *itemBody,
- })
- case *btrfsitem.Error:
- dlog.Errorf(ctx, "node@%v: item %v: error: malformed is EXTENT_CSUM: %v",
- nodeRef.Addr, i, itemBody.Err)
- default:
- panic(fmt.Errorf("should not happen: EXTENT_CSUM has unexpected item type: %T", itemBody))
- }
- }
- }
- minNextNode = pos + btrfsvol.PhysicalAddr(sb.NodeSize)
- }
- btrfstree.FreeNodeRef(nodeRef)
- }
- }
- progress(devSize)
- progressWriter.Done()
-
- result.Checksums = btrfssum.SumRun[btrfsvol.PhysicalAddr]{
- ChecksumSize: csumSize,
- Sums: btrfssum.ShortSum(sums.String()),
- }
-
- return result, nil
-}
diff --git a/lib/btrfsprogs/btrfsutil/broken_btree.go b/lib/btrfsprogs/btrfsutil/broken_btree.go
deleted file mode 100644
index b7663fa..0000000
--- a/lib/btrfsprogs/btrfsutil/broken_btree.go
+++ /dev/null
@@ -1,363 +0,0 @@
-// Copyright (C) 2022-2023 Luke Shumaker <lukeshu@lukeshu.com>
-//
-// SPDX-License-Identifier: GPL-2.0-or-later
-
-package btrfsutil
-
-import (
- "context"
- "fmt"
- iofs "io/fs"
- "sync"
-
- "github.com/datawire/dlib/derror"
- "github.com/datawire/dlib/dlog"
-
- "git.lukeshu.com/btrfs-progs-ng/lib/btrfs"
- "git.lukeshu.com/btrfs-progs-ng/lib/btrfs/btrfsprim"
- "git.lukeshu.com/btrfs-progs-ng/lib/btrfs/btrfstree"
- "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"
-)
-
-type treeIndex struct {
- TreeRootErr error
- Items *containers.RBTree[treeIndexValue]
- Errors *containers.IntervalTree[btrfsprim.Key, treeIndexError]
-}
-
-type treeIndexError struct {
- Path SkinnyPath
- Err error
-}
-
-type treeIndexValue struct {
- Path SkinnyPath
- Key btrfsprim.Key
- ItemSize uint32
-}
-
-// Compare implements containers.Ordered.
-func (a treeIndexValue) Compare(b treeIndexValue) int {
- return a.Key.Compare(b.Key)
-}
-
-func newTreeIndex(arena *SkinnyPathArena) treeIndex {
- return treeIndex{
- Items: new(containers.RBTree[treeIndexValue]),
- Errors: &containers.IntervalTree[btrfsprim.Key, treeIndexError]{
- MinFn: func(err treeIndexError) btrfsprim.Key {
- return arena.Inflate(err.Path).Node(-1).ToKey
- },
- MaxFn: func(err treeIndexError) btrfsprim.Key {
- return arena.Inflate(err.Path).Node(-1).ToMaxKey
- },
- },
- }
-}
-
-type brokenTrees struct {
- ctx context.Context //nolint:containedctx // don't have an option while keeping the same API
- inner *btrfs.FS
-
- arena *SkinnyPathArena
-
- // btrfsprim.ROOT_TREE_OBJECTID
- rootTreeMu sync.Mutex
- rootTreeIndex *treeIndex
- // for all other trees
- treeMu sync.Mutex
- treeIndexes map[btrfsprim.ObjID]treeIndex
-}
-
-var _ btrfstree.TreeOperator = (*brokenTrees)(nil)
-
-// NewBrokenTrees wraps a *btrfs.FS to support looking up information
-// from broken trees.
-//
-// Of the btrfstree.TreeOperator methods:
-//
-// - TreeWalk works on broken trees
-// - TreeLookup relies on the tree being properly ordered (which a
-// broken tree might not be).
-// - TreeSearch relies on the tree being properly ordered (which a
-// broken tree might not be).
-// - TreeSearchAll relies on the tree being properly ordered (which a
-// broken tree might not be), and a bad node may cause it to not
-// return a truncated list of results.
-//
-// NewBrokenTrees attempts to remedy these deficiencies by using
-// .TreeWalk to build an out-of-FS index of all of the items in the
-// tree, and re-implements TreeLookup, TreeSearch, and TreeSearchAll
-// using that index.
-func NewBrokenTrees(ctx context.Context, inner *btrfs.FS) interface {
- btrfstree.TreeOperator
- Superblock() (*btrfstree.Superblock, error)
- ReadAt(p []byte, off btrfsvol.LogicalAddr) (int, error)
- Augment(treeID btrfsprim.ObjID, nodeAddr btrfsvol.LogicalAddr) ([]btrfsprim.Key, error)
-} {
- return &brokenTrees{
- ctx: ctx,
- inner: inner,
- }
-}
-
-func (bt *brokenTrees) treeIndex(treeID btrfsprim.ObjID) treeIndex {
- var treeRoot *btrfstree.TreeRoot
- var sb *btrfstree.Superblock
- var err error
- if treeID == btrfsprim.ROOT_TREE_OBJECTID {
- bt.rootTreeMu.Lock()
- defer bt.rootTreeMu.Unlock()
- if bt.rootTreeIndex != nil {
- return *bt.rootTreeIndex
- }
- sb, err = bt.inner.Superblock()
- if err == nil {
- treeRoot, err = btrfstree.LookupTreeRoot(bt.inner, *sb, treeID)
- }
- } else {
- bt.treeMu.Lock()
- defer bt.treeMu.Unlock()
- if bt.treeIndexes == nil {
- bt.treeIndexes = make(map[btrfsprim.ObjID]treeIndex)
- }
- if cacheEntry, exists := bt.treeIndexes[treeID]; exists {
- return cacheEntry
- }
- sb, err = bt.inner.Superblock()
- if err == nil {
- treeRoot, err = btrfstree.LookupTreeRoot(bt, *sb, treeID)
- }
- }
- if bt.arena == nil {
- var _sb btrfstree.Superblock
- if sb != nil {
- _sb = *sb
- }
- bt.arena = &SkinnyPathArena{
- FS: bt.inner,
- SB: _sb,
- }
- }
- cacheEntry := newTreeIndex(bt.arena)
- if err != nil {
- cacheEntry.TreeRootErr = err
- } else {
- dlog.Infof(bt.ctx, "indexing tree %v...", treeID)
- bt.rawTreeWalk(*treeRoot, cacheEntry, nil)
- dlog.Infof(bt.ctx, "... done indexing tree %v", treeID)
- }
- if treeID == btrfsprim.ROOT_TREE_OBJECTID {
- bt.rootTreeIndex = &cacheEntry
- } else {
- bt.treeIndexes[treeID] = cacheEntry
- }
- return cacheEntry
-}
-
-func (bt *brokenTrees) rawTreeWalk(root btrfstree.TreeRoot, cacheEntry treeIndex, walked *[]btrfsprim.Key) {
- btrfstree.TreeOperatorImpl{NodeSource: bt.inner}.RawTreeWalk(
- bt.ctx,
- root,
- func(err *btrfstree.TreeError) {
- if len(err.Path) > 0 && err.Path.Node(-1).ToNodeAddr == 0 {
- // This is a panic because on the filesystems I'm working with it more likely
- // indicates a bug in my item parser than a problem with the filesystem.
- panic(fmt.Errorf("TODO: error parsing item: %w", err))
- }
- cacheEntry.Errors.Insert(treeIndexError{
- Path: bt.arena.Deflate(err.Path),
- Err: err.Err,
- })
- },
- btrfstree.TreeWalkHandler{
- Item: func(path btrfstree.TreePath, item btrfstree.Item) error {
- if cacheEntry.Items.Search(func(v treeIndexValue) int { return item.Key.Compare(v.Key) }) != nil {
- // This is a panic because I'm not really sure what the best way to
- // handle this is, and so if this happens I want the program to crash
- // and force me to figure out how to handle it.
- panic(fmt.Errorf("dup key=%v in tree=%v", item.Key, root.TreeID))
- }
- cacheEntry.Items.Insert(treeIndexValue{
- Path: bt.arena.Deflate(path),
- Key: item.Key,
- ItemSize: item.BodySize,
- })
- if walked != nil {
- *walked = append(*walked, item.Key)
- }
- return nil
- },
- },
- )
-}
-
-func (bt *brokenTrees) TreeLookup(treeID btrfsprim.ObjID, key btrfsprim.Key) (btrfstree.Item, error) {
- item, err := bt.TreeSearch(treeID, btrfstree.KeySearch(key.Compare))
- if err != nil {
- err = fmt.Errorf("item with key=%v: %w", key, err)
- }
- return item, err
-}
-
-func (bt *brokenTrees) addErrs(index treeIndex, fn func(btrfsprim.Key, uint32) int, err error) error {
- var errs derror.MultiError
- index.Errors.Subrange(
- func(k btrfsprim.Key) int { return fn(k, 0) },
- func(v treeIndexError) bool {
- errs = append(errs, &btrfstree.TreeError{
- Path: bt.arena.Inflate(v.Path),
- Err: v.Err,
- })
- return true
- })
- if len(errs) == 0 {
- return err
- }
- if err != nil {
- errs = append(errs, err)
- }
- return errs
-}
-
-func (bt *brokenTrees) TreeSearch(treeID btrfsprim.ObjID, fn func(btrfsprim.Key, uint32) int) (btrfstree.Item, error) {
- index := bt.treeIndex(treeID)
- if index.TreeRootErr != nil {
- return btrfstree.Item{}, index.TreeRootErr
- }
-
- indexItem := index.Items.Search(func(indexItem treeIndexValue) int {
- return fn(indexItem.Key, indexItem.ItemSize)
- })
- if indexItem == nil {
- return btrfstree.Item{}, bt.addErrs(index, fn, iofs.ErrNotExist)
- }
-
- itemPath := bt.arena.Inflate(indexItem.Value.Path)
- node, err := bt.inner.ReadNode(itemPath.Parent())
- defer btrfstree.FreeNodeRef(node)
- if err != nil {
- return btrfstree.Item{}, bt.addErrs(index, fn, err)
- }
-
- item := node.Data.BodyLeaf[itemPath.Node(-1).FromItemIdx]
- item.Body = item.Body.CloneItem()
-
- // Since we were only asked to return 1 item, it isn't
- // necessary to augment this `nil` with bt.addErrs().
- return item, nil
-}
-
-func (bt *brokenTrees) TreeSearchAll(treeID btrfsprim.ObjID, fn func(btrfsprim.Key, uint32) int) ([]btrfstree.Item, error) {
- index := bt.treeIndex(treeID)
- if index.TreeRootErr != nil {
- return nil, index.TreeRootErr
- }
-
- var indexItems []treeIndexValue
- index.Items.Subrange(
- func(indexItem treeIndexValue) int { return fn(indexItem.Key, indexItem.ItemSize) },
- func(node *containers.RBNode[treeIndexValue]) bool {
- indexItems = append(indexItems, node.Value)
- return true
- })
- if len(indexItems) == 0 {
- return nil, bt.addErrs(index, fn, iofs.ErrNotExist)
- }
-
- ret := make([]btrfstree.Item, len(indexItems))
- var node *diskio.Ref[btrfsvol.LogicalAddr, btrfstree.Node]
- for i := range indexItems {
- itemPath := bt.arena.Inflate(indexItems[i].Path)
- if node == nil || node.Addr != itemPath.Node(-2).ToNodeAddr {
- var err error
- btrfstree.FreeNodeRef(node)
- node, err = bt.inner.ReadNode(itemPath.Parent())
- if err != nil {
- btrfstree.FreeNodeRef(node)
- return nil, bt.addErrs(index, fn, err)
- }
- }
- ret[i] = node.Data.BodyLeaf[itemPath.Node(-1).FromItemIdx]
- ret[i].Body = ret[i].Body.CloneItem()
- }
- btrfstree.FreeNodeRef(node)
-
- return ret, bt.addErrs(index, fn, nil)
-}
-
-func (bt *brokenTrees) TreeWalk(ctx context.Context, treeID btrfsprim.ObjID, errHandle func(*btrfstree.TreeError), cbs btrfstree.TreeWalkHandler) {
- index := bt.treeIndex(treeID)
- if index.TreeRootErr != nil {
- errHandle(&btrfstree.TreeError{
- Path: btrfstree.TreePath{{
- FromTree: treeID,
- ToMaxKey: btrfsprim.MaxKey,
- }},
- Err: index.TreeRootErr,
- })
- return
- }
- var node *diskio.Ref[btrfsvol.LogicalAddr, btrfstree.Node]
- index.Items.Range(func(indexItem *containers.RBNode[treeIndexValue]) bool {
- if ctx.Err() != nil {
- return false
- }
- if bt.ctx.Err() != nil {
- return false
- }
- if cbs.Item != nil {
- itemPath := bt.arena.Inflate(indexItem.Value.Path)
- if node == nil || node.Addr != itemPath.Node(-2).ToNodeAddr {
- var err error
- btrfstree.FreeNodeRef(node)
- node, err = bt.inner.ReadNode(itemPath.Parent())
- if err != nil {
- btrfstree.FreeNodeRef(node)
- errHandle(&btrfstree.TreeError{Path: itemPath, Err: err})
- return true
- }
- }
- item := node.Data.BodyLeaf[itemPath.Node(-1).FromItemIdx]
- if err := cbs.Item(itemPath, item); err != nil {
- errHandle(&btrfstree.TreeError{Path: itemPath, Err: err})
- }
- }
- return true
- })
- btrfstree.FreeNodeRef(node)
-}
-
-func (bt *brokenTrees) Superblock() (*btrfstree.Superblock, error) {
- return bt.inner.Superblock()
-}
-
-func (bt *brokenTrees) ReadAt(p []byte, off btrfsvol.LogicalAddr) (int, error) {
- return bt.inner.ReadAt(p, off)
-}
-
-func (bt *brokenTrees) Augment(treeID btrfsprim.ObjID, nodeAddr btrfsvol.LogicalAddr) ([]btrfsprim.Key, error) {
- sb, err := bt.Superblock()
- if err != nil {
- return nil, err
- }
- index := bt.treeIndex(treeID)
- if index.TreeRootErr != nil {
- return nil, index.TreeRootErr
- }
- nodeRef, err := btrfstree.ReadNode[btrfsvol.LogicalAddr](bt.inner, *sb, nodeAddr, btrfstree.NodeExpectations{})
- defer btrfstree.FreeNodeRef(nodeRef)
- if err != nil {
- return nil, err
- }
- var ret []btrfsprim.Key
- bt.rawTreeWalk(btrfstree.TreeRoot{
- TreeID: treeID,
- RootNode: nodeAddr,
- Level: nodeRef.Data.Head.Level,
- Generation: nodeRef.Data.Head.Generation,
- }, index, &ret)
- return ret, nil
-}
diff --git a/lib/btrfsprogs/btrfsutil/open.go b/lib/btrfsprogs/btrfsutil/open.go
deleted file mode 100644
index c5ee314..0000000
--- a/lib/btrfsprogs/btrfsutil/open.go
+++ /dev/null
@@ -1,46 +0,0 @@
-// Copyright (C) 2022-2023 Luke Shumaker <lukeshu@lukeshu.com>
-//
-// SPDX-License-Identifier: GPL-2.0-or-later
-
-package btrfsutil
-
-import (
- "context"
- "fmt"
- "os"
-
- "github.com/datawire/dlib/dlog"
-
- "git.lukeshu.com/btrfs-progs-ng/lib/btrfs"
- "git.lukeshu.com/btrfs-progs-ng/lib/btrfs/btrfsvol"
- "git.lukeshu.com/btrfs-progs-ng/lib/diskio"
- "git.lukeshu.com/btrfs-progs-ng/lib/textui"
-)
-
-func Open(ctx context.Context, flag int, filenames ...string) (*btrfs.FS, error) {
- fs := new(btrfs.FS)
- for i, filename := range filenames {
- dlog.Debugf(ctx, "Adding device file %d/%d %q...", i, len(filenames), filename)
- osFile, err := os.OpenFile(filename, flag, 0)
- if err != nil {
- _ = fs.Close()
- return nil, fmt.Errorf("device file %q: %w", filename, err)
- }
- typedFile := &diskio.OSFile[btrfsvol.PhysicalAddr]{
- File: osFile,
- }
- bufFile := diskio.NewBufferedFile[btrfsvol.PhysicalAddr](
- typedFile,
- //nolint:gomnd // False positive: gomnd.ignored-functions=[textui.Tunable] doesn't support type params.
- textui.Tunable[btrfsvol.PhysicalAddr](16*1024), // block size: 16KiB
- textui.Tunable(1024), // number of blocks to buffer; total of 16MiB
- )
- devFile := &btrfs.Device{
- File: bufFile,
- }
- if err := fs.AddDevice(ctx, devFile); err != nil {
- return nil, fmt.Errorf("device file %q: %w", filename, err)
- }
- }
- return fs, nil
-}
diff --git a/lib/btrfsprogs/btrfsutil/skinny_paths.go b/lib/btrfsprogs/btrfsutil/skinny_paths.go
deleted file mode 100644
index 1695990..0000000
--- a/lib/btrfsprogs/btrfsutil/skinny_paths.go
+++ /dev/null
@@ -1,146 +0,0 @@
-// Copyright (C) 2022-2023 Luke Shumaker <lukeshu@lukeshu.com>
-//
-// SPDX-License-Identifier: GPL-2.0-or-later
-
-package btrfsutil
-
-import (
- "fmt"
-
- "git.lukeshu.com/btrfs-progs-ng/lib/btrfs/btrfstree"
- "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/textui"
-)
-
-type skinnyItem struct {
- Node btrfsvol.LogicalAddr
- Item int
-}
-
-type SkinnyPath struct {
- Root btrfsvol.LogicalAddr
- Items []int
-}
-
-type SkinnyPathArena struct {
- FS diskio.File[btrfsvol.LogicalAddr]
- SB btrfstree.Superblock
-
- fatRoots map[btrfsvol.LogicalAddr]btrfstree.TreePathElem
- fatItems containers.ARCache[skinnyItem, btrfstree.TreePathElem]
-}
-
-func (a *SkinnyPathArena) init() {
- if a.fatRoots == nil {
- a.fatRoots = make(map[btrfsvol.LogicalAddr]btrfstree.TreePathElem)
- a.fatItems.MaxLen = textui.Tunable(128 * 1024)
- }
-}
-
-func (a *SkinnyPathArena) getItem(parent btrfstree.TreePath, itemIdx int) (btrfstree.TreePathElem, error) {
- if itemIdx < 0 {
- panic("should not happen")
- }
-
- a.init()
-
- ret, ok := a.fatItems.Load(skinnyItem{
- Node: parent.Node(-1).ToNodeAddr,
- Item: itemIdx,
- })
- if ok {
- return ret, nil
- }
-
- node, err := btrfstree.ReadNode(a.FS, a.SB, parent.Node(-1).ToNodeAddr, btrfstree.NodeExpectations{})
- defer btrfstree.FreeNodeRef(node)
- if err != nil {
- return btrfstree.TreePathElem{}, err
- }
- if node.Data.Head.Level > 0 {
- if itemIdx >= len(node.Data.BodyInternal) {
- panic("should not happen")
- }
- for i, item := range node.Data.BodyInternal {
- toMaxKey := parent.Node(-1).ToMaxKey
- if i+1 < len(node.Data.BodyInternal) {
- toMaxKey = node.Data.BodyInternal[i+1].Key.Mm()
- }
- elem := btrfstree.TreePathElem{
- FromTree: node.Data.Head.Owner,
- FromItemIdx: i,
- ToNodeAddr: item.BlockPtr,
- ToNodeGeneration: item.Generation,
- ToNodeLevel: node.Data.Head.Level - 1,
- ToKey: item.Key,
- ToMaxKey: toMaxKey,
- }
- a.fatItems.Store(skinnyItem{Node: parent.Node(-1).ToNodeAddr, Item: i}, elem)
- if i == itemIdx {
- ret = elem
- }
- }
- } else {
- if itemIdx >= len(node.Data.BodyLeaf) {
- panic("should not happen")
- }
- for i, item := range node.Data.BodyLeaf {
- elem := btrfstree.TreePathElem{
- FromTree: node.Data.Head.Owner,
- FromItemIdx: i,
- ToKey: item.Key,
- ToMaxKey: item.Key,
- }
- a.fatItems.Store(skinnyItem{Node: parent.Node(-1).ToNodeAddr, Item: i}, elem)
- if i == itemIdx {
- ret = elem
- }
- }
- }
-
- return ret, nil
-}
-
-func (a *SkinnyPathArena) Deflate(fat btrfstree.TreePath) SkinnyPath {
- a.init()
-
- var ret SkinnyPath
-
- var prevNode btrfsvol.LogicalAddr
- for i, elem := range fat {
- if i == 0 {
- a.fatRoots[elem.ToNodeAddr] = elem
- ret.Root = elem.ToNodeAddr
- } else {
- a.fatItems.Store(skinnyItem{Node: prevNode, Item: elem.FromItemIdx}, elem)
- ret.Items = append(ret.Items, elem.FromItemIdx)
- }
- prevNode = elem.ToNodeAddr
- }
- return ret
-}
-
-func (a *SkinnyPathArena) Inflate(skinny SkinnyPath) btrfstree.TreePath {
- a.init()
-
- ret := make(btrfstree.TreePath, 0, 1+len(skinny.Items))
-
- root, ok := a.fatRoots[skinny.Root]
- if !ok {
- panic(fmt.Errorf("SkinnyPathArena.Inflate: no stored TreePathElem for root->%v",
- skinny.Root))
- }
- ret = append(ret, root)
-
- for _, itemIdx := range skinny.Items {
- elem, err := a.getItem(ret, itemIdx)
- if err != nil {
- panic(err)
- }
- ret = append(ret, elem)
- }
-
- return ret
-}
diff --git a/lib/btrfsprogs/btrfsutil/walk.go b/lib/btrfsprogs/btrfsutil/walk.go
deleted file mode 100644
index 355976a..0000000
--- a/lib/btrfsprogs/btrfsutil/walk.go
+++ /dev/null
@@ -1,97 +0,0 @@
-// Copyright (C) 2022 Luke Shumaker <lukeshu@lukeshu.com>
-//
-// SPDX-License-Identifier: GPL-2.0-or-later
-
-package btrfsutil
-
-import (
- "context"
- "fmt"
-
- "git.lukeshu.com/btrfs-progs-ng/lib/btrfs/btrfsitem"
- "git.lukeshu.com/btrfs-progs-ng/lib/btrfs/btrfsprim"
- "git.lukeshu.com/btrfs-progs-ng/lib/btrfs/btrfstree"
-)
-
-type WalkError struct {
- TreeName string
- Err *btrfstree.TreeError
-}
-
-func (e *WalkError) Unwrap() error { return e.Err }
-
-func (e *WalkError) Error() string {
- return fmt.Sprintf("%v: %v", e.TreeName, e.Err)
-}
-
-type WalkAllTreesHandler struct {
- Err func(*WalkError)
- // Callbacks for entire trees
- PreTree func(name string, id btrfsprim.ObjID)
- PostTree func(name string, id btrfsprim.ObjID)
- // Callbacks for nodes or smaller
- btrfstree.TreeWalkHandler
-}
-
-// WalkAllTrees walks all trees in a *btrfs.FS. Rather than returning
-// an error, it calls errCb each time an error is encountered. The
-// error will always be of type WalkError.
-func WalkAllTrees(ctx context.Context, fs btrfstree.TreeOperator, cbs WalkAllTreesHandler) {
- var treeName string
-
- trees := []struct {
- Name string
- ID btrfsprim.ObjID
- }{
- {
- Name: "root tree",
- ID: btrfsprim.ROOT_TREE_OBJECTID,
- },
- {
- Name: "chunk tree",
- ID: btrfsprim.CHUNK_TREE_OBJECTID,
- },
- {
- Name: "log tree",
- ID: btrfsprim.TREE_LOG_OBJECTID,
- },
- {
- Name: "block group tree",
- ID: btrfsprim.BLOCK_GROUP_TREE_OBJECTID,
- },
- }
- origItem := cbs.Item
- cbs.Item = func(path btrfstree.TreePath, item btrfstree.Item) error {
- if item.Key.ItemType == btrfsitem.ROOT_ITEM_KEY {
- trees = append(trees, struct {
- Name string
- ID btrfsprim.ObjID
- }{
- Name: fmt.Sprintf("tree %v (via %v %v)",
- item.Key.ObjectID.Format(0), treeName, path),
- ID: item.Key.ObjectID,
- })
- }
- if origItem != nil {
- return origItem(path, item)
- }
- return nil
- }
-
- for i := 0; i < len(trees); i++ {
- tree := trees[i]
- treeName = tree.Name
- if cbs.PreTree != nil {
- cbs.PreTree(treeName, tree.ID)
- }
- fs.TreeWalk(
- ctx,
- tree.ID,
- func(err *btrfstree.TreeError) { cbs.Err(&WalkError{TreeName: treeName, Err: err}) },
- cbs.TreeWalkHandler,
- )
- if cbs.PostTree != nil {
- cbs.PostTree(treeName, tree.ID)
- }
- }
-}