summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-rw-r--r--cmd/btrfs-rec/inspect/rebuildtrees/rebuild_treecb.go40
-rw-r--r--cmd/btrfs-rec/main.go33
-rw-r--r--lib/btrfsutil/old_rebuilt_forrest.go471
-rw-r--r--lib/btrfsutil/rebuilt_callbacks.go42
-rw-r--r--lib/btrfsutil/rebuilt_forrest.go67
-rw-r--r--lib/btrfsutil/rebuilt_tree.go4
-rwxr-xr-xscripts/main.sh12
7 files changed, 157 insertions, 512 deletions
diff --git a/cmd/btrfs-rec/inspect/rebuildtrees/rebuild_treecb.go b/cmd/btrfs-rec/inspect/rebuildtrees/rebuild_treecb.go
index b8205ae..466082c 100644
--- a/cmd/btrfs-rec/inspect/rebuildtrees/rebuild_treecb.go
+++ b/cmd/btrfs-rec/inspect/rebuildtrees/rebuild_treecb.go
@@ -75,7 +75,9 @@ func (o forrestCallbacks) LookupUUID(ctx context.Context, uuid btrfsprim.UUID) (
}
ctx = withWant(ctx, logFieldTreeWant, "resolve parent UUID", wantKey)
if !o._wantOff(ctx, wantKey) {
- o.enqueueRetry(btrfsprim.UUID_TREE_OBJECTID)
+ if id, ok := o.slowLookupUUID(ctx, uuid); ok {
+ return id, nil
+ }
return 0, btrfstree.ErrNoItem
}
item, _ := discardErr(o.rebuilt.RebuiltTree(ctx, wantKey.TreeID)).TreeLookup(ctx, wantKey.Key.Key())
@@ -85,6 +87,9 @@ func (o forrestCallbacks) LookupUUID(ctx context.Context, uuid btrfsprim.UUID) (
return itemBody.ObjID, nil
case *btrfsitem.Error:
graphCallbacks(o).FSErr(ctx, fmt.Errorf("error decoding item: %v: %w", wantKey, itemBody.Err))
+ if id, ok := o.slowLookupUUID(ctx, uuid); ok {
+ return id, nil
+ }
return 0, itemBody.Err
default:
// This is a panic because the item decoder should not emit UUID_SUBVOL items as anything but
@@ -92,3 +97,36 @@ func (o forrestCallbacks) LookupUUID(ctx context.Context, uuid btrfsprim.UUID) (
panic(fmt.Errorf("should not happen: UUID_SUBVOL item has unexpected type: %T", itemBody))
}
}
+
+func (o forrestCallbacks) slowLookupUUID(ctx context.Context, uuid btrfsprim.UUID) (id btrfsprim.ObjID, ok bool) {
+ rootTree, err := o.rebuilt.RebuiltTree(ctx, btrfsprim.ROOT_TREE_OBJECTID)
+ if err != nil {
+ o.enqueueRetry(btrfsprim.ROOT_TREE_OBJECTID)
+ return 0, false
+ }
+ var ret btrfsprim.ObjID
+ _ = rootTree.TreeRange(ctx, func(item btrfstree.Item) bool {
+ if item.Key.ItemType != btrfsprim.ROOT_ITEM_KEY {
+ return true
+ }
+ switch itemBody := item.Body.(type) {
+ case *btrfsitem.Root:
+ if itemBody.UUID == uuid {
+ ret = item.Key.ObjectID
+ return false
+ }
+ case *btrfsitem.Error:
+ graphCallbacks(o).FSErr(ctx, fmt.Errorf("error decoding item: %v: %w", item.Key, itemBody.Err))
+ 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))
+ }
+ return true
+ })
+ if ret == 0 {
+ o.enqueueRetry(btrfsprim.ROOT_TREE_OBJECTID)
+ return 0, false
+ }
+ return ret, true
+}
diff --git a/cmd/btrfs-rec/main.go b/cmd/btrfs-rec/main.go
index ad768de..39ba9ef 100644
--- a/cmd/btrfs-rec/main.go
+++ b/cmd/btrfs-rec/main.go
@@ -17,8 +17,10 @@ import (
"github.com/spf13/cobra"
"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/btrfsvol"
"git.lukeshu.com/btrfs-progs-ng/lib/btrfsutil"
+ "git.lukeshu.com/btrfs-progs-ng/lib/containers"
"git.lukeshu.com/btrfs-progs-ng/lib/profile"
"git.lukeshu.com/btrfs-progs-ng/lib/textui"
)
@@ -51,8 +53,8 @@ var globalFlags struct {
mappings string
nodeList string
- rebuildV1 bool
- rebuildV2 bool
+ rebuild bool
+ treeRoots string
stopProfiling profile.StopFunc
@@ -102,11 +104,12 @@ func main() {
"load node list (output of 'btrfs-recs inspect [rebuild-mappings] list-nodes') from external JSON file `nodes.json`")
noError(argparser.MarkPersistentFlagFilename("node-list"))
- argparser.PersistentFlags().BoolVar(&globalFlags.rebuildV1, "rebuild", false,
- "attempt to rebuild broken btrees when reading (v1)")
+ argparser.PersistentFlags().BoolVar(&globalFlags.rebuild, "rebuild", false,
+ "attempt to rebuild broken btrees when reading")
- argparser.PersistentFlags().BoolVar(&globalFlags.rebuildV2, "rebuild-v2", false,
- "attempt to rebuild broken btrees when reading (v2)")
+ argparser.PersistentFlags().StringVar(&globalFlags.treeRoots, "trees", "",
+ "load list of tree roots (output of 'btrfs-recs inspect rebuild-trees') from external JSON file `trees.json`; implies --rebuild")
+ noError(argparser.MarkPersistentFlagFilename("trees"))
globalFlags.stopProfiling = profile.AddProfileFlags(argparser.PersistentFlags(), "profile.")
@@ -214,9 +217,7 @@ func runWithRawFSAndNodeList(runE func(*btrfs.FS, []btrfsvol.LogicalAddr, *cobra
func _runWithReadableFS(wantNodeList bool, runE func(btrfs.ReadableFS, []btrfsvol.LogicalAddr, *cobra.Command, []string) error) func(*cobra.Command, []string) error {
inner := func(fs *btrfs.FS, nodeList []btrfsvol.LogicalAddr, cmd *cobra.Command, args []string) error {
var rfs btrfs.ReadableFS = fs
- if globalFlags.rebuildV1 {
- rfs = btrfsutil.NewOldRebuiltForrest(fs)
- } else if globalFlags.rebuildV2 {
+ if globalFlags.rebuild || globalFlags.treeRoots != "" {
ctx := cmd.Context()
graph, err := btrfsutil.ReadGraph(ctx, fs, nodeList)
@@ -224,14 +225,24 @@ func _runWithReadableFS(wantNodeList bool, runE func(btrfs.ReadableFS, []btrfsvo
return err
}
- rfs = btrfsutil.NewRebuiltForrest(fs, graph, nil, true)
+ _rfs := btrfsutil.NewRebuiltForrest(fs, graph, nil, true)
+
+ if globalFlags.treeRoots != "" {
+ roots, err := readJSONFile[map[btrfsprim.ObjID]containers.Set[btrfsvol.LogicalAddr]](ctx, globalFlags.treeRoots)
+ if err != nil {
+ return err
+ }
+ _rfs.RebuiltAddRoots(ctx, roots)
+ }
+
+ rfs = _rfs
}
return runE(rfs, nodeList, cmd, args)
}
return func(cmd *cobra.Command, args []string) error {
- if wantNodeList || globalFlags.rebuildV2 {
+ if wantNodeList || globalFlags.rebuild || globalFlags.treeRoots != "" {
return runWithRawFSAndNodeList(inner)(cmd, args)
}
return runWithRawFS(func(fs *btrfs.FS, cmd *cobra.Command, args []string) error {
diff --git a/lib/btrfsutil/old_rebuilt_forrest.go b/lib/btrfsutil/old_rebuilt_forrest.go
deleted file mode 100644
index a23278c..0000000
--- a/lib/btrfsutil/old_rebuilt_forrest.go
+++ /dev/null
@@ -1,471 +0,0 @@
-// Copyright (C) 2022-2023 Luke Shumaker <lukeshu@lukeshu.com>
-//
-// SPDX-License-Identifier: GPL-2.0-or-later
-
-package btrfsutil
-
-import (
- "context"
- "fmt"
- "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/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"
-)
-
-type oldRebuiltTree struct {
- forrest *OldRebuiltForrest
-
- ID btrfsprim.ObjID
- ParentUUID btrfsprim.UUID
- ParentGen btrfsprim.Generation // offset of this tree's root item
-
- RootErr error
- Items *containers.RBTree[oldRebuiltTreeValue]
- Errors *containers.IntervalTree[btrfsprim.Key, oldRebuiltTreeError]
-}
-
-var _ btrfstree.Tree = oldRebuiltTree{}
-
-type oldRebuiltTreeError struct {
- Min btrfsprim.Key
- Max btrfsprim.Key
- Node btrfsvol.LogicalAddr
- Err error
-}
-
-func (e oldRebuiltTreeError) Error() string {
- return fmt.Sprintf("keys %v-%v: node@%v: %v", e.Min, e.Max, e.Node, e.Err)
-}
-
-func (e oldRebuiltTreeError) Unwrap() error {
- return e.Err
-}
-
-type oldRebuiltTreeValue struct {
- Key btrfsprim.Key
- ItemSize uint32
-
- Node oldRebuiltNodeInfo
- Slot int
-}
-
-type oldRebuiltNodeInfo struct {
- LAddr btrfsvol.LogicalAddr
- Level uint8
- Generation btrfsprim.Generation
- Owner btrfsprim.ObjID
- MinItem btrfsprim.Key
- MaxItem btrfsprim.Key
-}
-
-// Compare implements containers.Ordered.
-func (a oldRebuiltTreeValue) Compare(b oldRebuiltTreeValue) int {
- return a.Key.Compare(b.Key)
-}
-
-func newOldRebuiltTree() oldRebuiltTree {
- return oldRebuiltTree{
- Items: new(containers.RBTree[oldRebuiltTreeValue]),
- Errors: &containers.IntervalTree[btrfsprim.Key, oldRebuiltTreeError]{
- MinFn: func(err oldRebuiltTreeError) btrfsprim.Key {
- return err.Min
- },
- MaxFn: func(err oldRebuiltTreeError) btrfsprim.Key {
- return err.Max
- },
- },
- }
-}
-
-type OldRebuiltForrest struct {
- inner *btrfs.FS
-
- // btrfsprim.ROOT_TREE_OBJECTID
- rootTreeMu sync.Mutex
- rootTree *oldRebuiltTree
- // for all other trees
- treesMu sync.Mutex
- trees map[btrfsprim.ObjID]oldRebuiltTree
-}
-
-var _ btrfs.ReadableFS = (*OldRebuiltForrest)(nil)
-
-// NewOldRebuiltForrest wraps a *btrfs.FS to support looking up
-// information from broken trees.
-//
-// Of the btrfstree.Tree methods:
-//
-// - TreeRange works on broken trees
-// - TreeSubrange 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).
-// - TreeLookup relies on the tree being properly ordered (which a
-// broken tree might not be).
-//
-// NewOldRebuiltForrest attempts to remedy these deficiencies by
-// building an out-of-FS index of all of the items in the tree, and
-// re-implements TreeLookup, TreeSearch, TreeSubrange, and TreeRange
-// using that index.
-func NewOldRebuiltForrest(inner *btrfs.FS) *OldRebuiltForrest {
- return &OldRebuiltForrest{
- inner: inner,
- }
-}
-
-// ForrestLookup implements btrfstree.Forrest.
-func (bt *OldRebuiltForrest) ForrestLookup(ctx context.Context, treeID btrfsprim.ObjID) (btrfstree.Tree, error) {
- tree := bt.RebuiltTree(ctx, treeID)
- if tree.RootErr != nil {
- return nil, tree.RootErr
- }
- return tree, nil
-}
-
-// RebuiltTree is a variant of ForrestLookup that returns a concrete
-// type instead of an interface. An error is indicated by the
-// ret.RootErr member.
-func (bt *OldRebuiltForrest) RebuiltTree(ctx context.Context, treeID btrfsprim.ObjID) oldRebuiltTree {
- if treeID == btrfsprim.ROOT_TREE_OBJECTID {
- bt.rootTreeMu.Lock()
- defer bt.rootTreeMu.Unlock()
- if bt.rootTree != nil {
- return *bt.rootTree
- }
- } else {
- bt.treesMu.Lock()
- defer bt.treesMu.Unlock()
- if bt.trees == nil {
- bt.trees = make(map[btrfsprim.ObjID]oldRebuiltTree)
- }
- if cacheEntry, exists := bt.trees[treeID]; exists {
- return cacheEntry
- }
- }
-
- cacheEntry := newOldRebuiltTree()
- cacheEntry.forrest = bt
- cacheEntry.ID = treeID
- dlog.Infof(ctx, "indexing tree %v...", treeID)
- bt.rawTreeWalk(ctx, treeID, &cacheEntry)
- dlog.Infof(ctx, "... done indexing tree %v", treeID)
-
- if treeID == btrfsprim.ROOT_TREE_OBJECTID {
- bt.rootTree = &cacheEntry
- } else {
- bt.trees[treeID] = cacheEntry
- }
- return cacheEntry
-}
-
-func discardOK[T any](x T, _ bool) T { return x }
-
-func (bt *OldRebuiltForrest) rawTreeWalk(ctx context.Context, treeID btrfsprim.ObjID, cacheEntry *oldRebuiltTree) {
- sb, err := bt.inner.Superblock()
- if err != nil {
- cacheEntry.RootErr = err
- return
- }
- root, err := btrfstree.LookupTreeRoot(ctx, bt, *sb, treeID)
- if err != nil {
- cacheEntry.RootErr = err
- return
- }
- tree := &btrfstree.RawTree{
- Forrest: btrfstree.RawForrest{NodeSource: bt.inner},
- TreeRoot: *root,
- }
-
- cacheEntry.ParentUUID = root.ParentUUID
- cacheEntry.ParentGen = root.ParentGen
-
- var curNode oldRebuiltNodeInfo
- cbs := btrfstree.TreeWalkHandler{
- BadNode: func(path btrfstree.Path, node *btrfstree.Node, err error) bool {
- nodeAddr, nodeExp, _ := path.NodeExpectations(ctx)
- cacheEntry.Errors.Insert(oldRebuiltTreeError{
- Min: nodeExp.MinItem.Val,
- Max: nodeExp.MaxItem.Val,
- Node: nodeAddr,
- Err: err,
- })
- return false
- },
- Node: func(path btrfstree.Path, node *btrfstree.Node) {
- curNode = oldRebuiltNodeInfo{
- LAddr: node.Head.Addr,
- Level: node.Head.Level,
- Generation: node.Head.Generation,
- Owner: node.Head.Owner,
- MinItem: discardOK(node.MinItem()),
- MaxItem: discardOK(node.MaxItem()),
- }
- },
- Item: func(path btrfstree.Path, item btrfstree.Item) {
- if cacheEntry.Items.Search(func(v oldRebuiltTreeValue) 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, treeID))
- }
- cacheEntry.Items.Insert(oldRebuiltTreeValue{
- Key: item.Key,
- ItemSize: item.BodySize,
-
- Node: curNode,
- Slot: path[len(path)-1].(btrfstree.PathItem).FromSlot, //nolint:forcetypeassert // has to be
- })
- },
- }
- cbs.BadItem = cbs.Item
-
- tree.TreeWalk(ctx, cbs)
-}
-
-func (tree oldRebuiltTree) addErrs(fn func(btrfsprim.Key, uint32) int, err error) error {
- var errs derror.MultiError
- tree.Errors.Subrange(
- func(k btrfsprim.Key) int { return fn(k, 0) },
- func(v oldRebuiltTreeError) bool {
- errs = append(errs, v)
- return true
- })
- if len(errs) == 0 {
- return err
- }
- if err != nil {
- errs = append(errs, err)
- }
- return errs
-}
-
-func (bt *OldRebuiltForrest) readNode(ctx context.Context, nodeInfo oldRebuiltNodeInfo) *btrfstree.Node {
- node, err := bt.AcquireNode(ctx, nodeInfo.LAddr, btrfstree.NodeExpectations{
- LAddr: containers.OptionalValue(nodeInfo.LAddr),
- Level: containers.OptionalValue(nodeInfo.Level),
- Generation: containers.OptionalValue(nodeInfo.Generation),
- Owner: func(treeID btrfsprim.ObjID, gen btrfsprim.Generation) error {
- if treeID != nodeInfo.Owner || gen != nodeInfo.Generation {
- return fmt.Errorf("expected owner=%v generation=%v but claims to have owner=%v generation=%v",
- nodeInfo.Owner, nodeInfo.Generation,
- treeID, gen)
- }
- return nil
- },
- MinItem: containers.OptionalValue(nodeInfo.MinItem),
- MaxItem: containers.OptionalValue(nodeInfo.MaxItem),
- })
- if err != nil {
- panic(fmt.Errorf("should not happen: i/o error: %w", err))
- }
-
- return node
-}
-
-// TreeLookup implements btrfstree.Tree.
-func (tree oldRebuiltTree) TreeLookup(ctx context.Context, key btrfsprim.Key) (btrfstree.Item, error) {
- return tree.TreeSearch(ctx, btrfstree.SearchExactKey(key))
-}
-
-// TreeSearch implements btrfstree.Tree.
-func (tree oldRebuiltTree) TreeSearch(ctx context.Context, searcher btrfstree.TreeSearcher) (btrfstree.Item, error) {
- if tree.RootErr != nil {
- return btrfstree.Item{}, tree.RootErr
- }
-
- indexItem := tree.Items.Search(func(indexItem oldRebuiltTreeValue) int {
- return searcher.Search(indexItem.Key, indexItem.ItemSize)
- })
- if indexItem == nil {
- return btrfstree.Item{}, fmt.Errorf("item with %s: %w", searcher, tree.addErrs(searcher.Search, btrfstree.ErrNoItem))
- }
-
- node := tree.forrest.readNode(ctx, indexItem.Value.Node)
- defer tree.forrest.ReleaseNode(node)
-
- item := node.BodyLeaf[indexItem.Value.Slot]
- item.Body = item.Body.CloneItem()
-
- // Since we were only asked to return 1 item, it isn't
- // necessary to augment this `nil` with tree.addErrs().
- return item, nil
-}
-
-// TreeRange implements btrfstree.Tree.
-func (tree oldRebuiltTree) TreeRange(ctx context.Context, handleFn func(btrfstree.Item) bool) error {
- if tree.RootErr != nil {
- return tree.RootErr
- }
-
- var node *btrfstree.Node
- tree.Items.Range(
- func(rbnode *containers.RBNode[oldRebuiltTreeValue]) bool {
- if node == nil || node.Head.Addr != rbnode.Value.Node.LAddr {
- tree.forrest.ReleaseNode(node)
- node = tree.forrest.readNode(ctx, rbnode.Value.Node)
- }
- return handleFn(node.BodyLeaf[rbnode.Value.Slot])
- })
- tree.forrest.ReleaseNode(node)
-
- return tree.addErrs(func(btrfsprim.Key, uint32) int { return 0 }, nil)
-}
-
-// TreeSubrange implements btrfstree.Tree.
-func (tree oldRebuiltTree) TreeSubrange(ctx context.Context, min int, searcher btrfstree.TreeSearcher, handleFn func(btrfstree.Item) bool) error {
- var node *btrfstree.Node
- var cnt int
- tree.Items.Subrange(
- func(indexItem oldRebuiltTreeValue) int {
- return searcher.Search(indexItem.Key, indexItem.ItemSize)
- },
- func(rbNode *containers.RBNode[oldRebuiltTreeValue]) bool {
- cnt++
- if node == nil || node.Head.Addr != rbNode.Value.Node.LAddr {
- tree.forrest.ReleaseNode(node)
- node = tree.forrest.readNode(ctx, rbNode.Value.Node)
- }
- return handleFn(node.BodyLeaf[rbNode.Value.Slot])
- })
- tree.forrest.ReleaseNode(node)
-
- var err error
- if cnt < min {
- err = btrfstree.ErrNoItem
- }
- err = tree.addErrs(searcher.Search, err)
- if err != nil {
- err = fmt.Errorf("items with %s: %w", searcher, err)
- }
- return err
-}
-
-// TreeWalk implements btrfstree.Tree. It only visits items and valid
-// leaf nodes (not the superblock, interior nodes, or bad nodes).
-func (tree oldRebuiltTree) TreeWalk(ctx context.Context, cbs btrfstree.TreeWalkHandler) {
- if cbs.Node == nil && cbs.Item == nil && cbs.BadItem == nil {
- return
- }
- visitedNodes := make(containers.Set[btrfsvol.LogicalAddr])
- var node *btrfstree.Node
- tree.Items.Range(func(indexItem *containers.RBNode[oldRebuiltTreeValue]) bool {
- if ctx.Err() != nil {
- return false
- }
-
- if node == nil || node.Head.Addr != indexItem.Value.Node.LAddr {
- tree.forrest.ReleaseNode(node)
- node = tree.forrest.readNode(ctx, indexItem.Value.Node)
- if cbs.Node != nil && !visitedNodes.Has(indexItem.Value.Node.LAddr) {
- nodePath := btrfstree.Path{
- btrfstree.PathRoot{
- Forrest: tree.forrest,
- TreeID: tree.ID,
- ToAddr: indexItem.Value.Node.LAddr,
- ToGeneration: indexItem.Value.Node.Generation,
- ToLevel: indexItem.Value.Node.Level,
- },
- }
- cbs.Node(nodePath, node)
- if ctx.Err() != nil {
- return false
- }
- visitedNodes.Insert(indexItem.Value.Node.LAddr)
- }
- }
-
- if cbs.Item != nil || cbs.BadItem != nil {
- item := node.BodyLeaf[indexItem.Value.Slot]
- itemPath := btrfstree.Path{
- btrfstree.PathRoot{
- Forrest: tree.forrest,
- TreeID: tree.ID,
- ToAddr: indexItem.Value.Node.LAddr,
- ToGeneration: indexItem.Value.Node.Generation,
- ToLevel: indexItem.Value.Node.Level,
- },
- btrfstree.PathItem{
- FromTree: indexItem.Value.Node.Owner,
- FromSlot: indexItem.Value.Slot,
- ToKey: indexItem.Value.Key,
- },
- }
- switch item.Body.(type) {
- case *btrfsitem.Error:
- if cbs.BadItem != nil {
- cbs.BadItem(itemPath, item)
- }
- default:
- if cbs.Item != nil {
- cbs.Item(itemPath, item)
- }
- }
- if ctx.Err() != nil {
- return false
- }
- }
-
- return true
- })
- tree.forrest.ReleaseNode(node)
-}
-
-// TreeParentID implements btrfstree.Tree.
-func (tree oldRebuiltTree) TreeParentID(ctx context.Context) (btrfsprim.ObjID, btrfsprim.Generation, error) {
- if tree.ParentUUID == (btrfsprim.UUID{}) {
- return 0, 0, nil
- }
- uuidTree := tree.forrest.RebuiltTree(ctx, btrfsprim.UUID_TREE_OBJECTID)
- if uuidTree.RootErr != nil {
- return 0, 0, uuidTree.RootErr
- }
- parentIDItem, err := uuidTree.TreeLookup(ctx, btrfsitem.UUIDToKey(tree.ParentUUID))
- if err != nil {
- return 0, 0, err
- }
- switch parentIDBody := parentIDItem.Body.(type) {
- case *btrfsitem.UUIDMap:
- return parentIDBody.ObjID, tree.ParentGen, nil
- case *btrfsitem.Error:
- return 0, 0, parentIDBody.Err
- 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", parentIDBody))
- }
-}
-
-// btrfs.ReadableFS (other than btrfstree.Forrest) /////////////////////////////////////////////////////////////////////
-
-// Name implements btrfs.ReadableFS.
-func (bt *OldRebuiltForrest) Name() string {
- return bt.inner.Name()
-}
-
-// Superblock implements btrfstree.NodeSource (and btrfs.ReadableFS).
-func (bt *OldRebuiltForrest) Superblock() (*btrfstree.Superblock, error) {
- return bt.inner.Superblock()
-}
-
-// AcquireNode implements btrfstree.NodeSource (and btrfs.ReadableFS).
-func (bt *OldRebuiltForrest) AcquireNode(ctx context.Context, addr btrfsvol.LogicalAddr, exp btrfstree.NodeExpectations) (*btrfstree.Node, error) {
- return bt.inner.AcquireNode(ctx, addr, exp)
-}
-
-// ReleaseNode implements btrfstree.NodeSource (and btrfs.ReadableFS).
-func (bt *OldRebuiltForrest) ReleaseNode(node *btrfstree.Node) {
- bt.inner.ReleaseNode(node)
-}
-
-// ReadAt implements diskio.ReaderAt[btrfsvol.LogicalAddr] (and btrfs.ReadableFS).
-func (bt *OldRebuiltForrest) ReadAt(p []byte, off btrfsvol.LogicalAddr) (int, error) {
- return bt.inner.ReadAt(p, off)
-}
diff --git a/lib/btrfsutil/rebuilt_callbacks.go b/lib/btrfsutil/rebuilt_callbacks.go
index b5fbc91..8d96c41 100644
--- a/lib/btrfsutil/rebuilt_callbacks.go
+++ b/lib/btrfsutil/rebuilt_callbacks.go
@@ -57,11 +57,17 @@ func (cb noopRebuiltForrestCallbacks) LookupRoot(ctx context.Context, tree btrfs
func (cb noopRebuiltForrestCallbacks) LookupUUID(ctx context.Context, uuid btrfsprim.UUID) (id btrfsprim.ObjID, err error) {
uuidTree, err := cb.forrest.ForrestLookup(ctx, btrfsprim.UUID_TREE_OBJECTID)
if err != nil {
+ if id, ok := cb.slowLookupUUID(ctx, uuid); ok {
+ return id, nil
+ }
return 0, err
}
tgt := btrfsitem.UUIDToKey(uuid)
item, err := uuidTree.TreeLookup(ctx, tgt)
if err != nil {
+ if id, ok := cb.slowLookupUUID(ctx, uuid); ok {
+ return id, nil
+ }
return 0, err
}
defer item.Body.Free()
@@ -69,10 +75,44 @@ func (cb noopRebuiltForrestCallbacks) LookupUUID(ctx context.Context, uuid btrfs
case *btrfsitem.UUIDMap:
return itemBody.ObjID, nil
case *btrfsitem.Error:
- return 0, itemBody.Err
+ if id, ok := cb.slowLookupUUID(ctx, uuid); ok {
+ return id, nil
+ }
+ return 0, err
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))
}
}
+
+func (cb noopRebuiltForrestCallbacks) slowLookupUUID(ctx context.Context, uuid btrfsprim.UUID) (id btrfsprim.ObjID, ok bool) {
+ rootTree, err := cb.forrest.ForrestLookup(ctx, btrfsprim.ROOT_TREE_OBJECTID)
+ if err != nil {
+ return 0, false
+ }
+ var ret btrfsprim.ObjID
+ _ = rootTree.TreeRange(ctx, func(item btrfstree.Item) bool {
+ if item.Key.ItemType != btrfsprim.ROOT_ITEM_KEY {
+ return true
+ }
+ switch itemBody := item.Body.(type) {
+ case *btrfsitem.Root:
+ if itemBody.UUID == uuid {
+ ret = item.Key.ObjectID
+ return false
+ }
+ case *btrfsitem.Error:
+ // do nothing
+ 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))
+ }
+ return true
+ })
+ if ret == 0 {
+ return 0, false
+ }
+ return ret, true
+}
diff --git a/lib/btrfsutil/rebuilt_forrest.go b/lib/btrfsutil/rebuilt_forrest.go
index 79d8beb..4ce2435 100644
--- a/lib/btrfsutil/rebuilt_forrest.go
+++ b/lib/btrfsutil/rebuilt_forrest.go
@@ -23,29 +23,18 @@ import (
// RebuiltForrest is an abstraction for rebuilding and accessing
// potentially broken btrees.
//
-// It is conceptually a btrfstree.Forrest, and adds similar
-// broken-tree handling to OldRebuiltForrest. However, it is much
-// more efficient than OldRebuiltForrest.
+// Additionally, it provides some functionality on top of a vanilla
+// btrfs.ReadableFS:
//
-// The efficiency improvements are possible because of the API
-// differences, which are necessary for how it is used in
-// rebuildtrees:
-//
-// - it consumes an already-read Graph instead of reading the graph
-// itself
-//
-// - it does not use `btrfstree.Path`
-//
-// - it does not keep track of errors encountered in a tree
-//
-// Additionally, it provides some functionality that OldRebuiltForrest
-// does not:
+// - it provides a RebuiltTree.RebuiltAddRoot() method for repairing a
+// tree.
//
// - it provides a RebuiltForrest.RebuiltListRoots() method for
// listing how trees have been repaired.
//
-// - it provides a RebuiltTree.RebuiltAddRoot() method for repairing a
-// tree.
+// - it provides a RebuiltForrest.RebuiltAddRoots() method for
+// batch-loading the results from
+// RebuiltForrest.RebuiltListroots().
//
// - it provides several RebuiltTree methods that provide advice on
// what roots should be added to a tree in order to repair it:
@@ -275,6 +264,48 @@ func (ts *RebuiltForrest) RebuiltListRoots(ctx context.Context) map[btrfsprim.Ob
return ret
}
+// RebuiltAddRoots takes a listing of the root nodes for trees (as
+// returned by RebuiltListRoots), and augments the trees to include
+// them.
+func (ts *RebuiltForrest) RebuiltAddRoots(ctx context.Context, roots map[btrfsprim.ObjID]containers.Set[btrfsvol.LogicalAddr]) {
+ ctx = ts.treesMu.Lock(ctx)
+ defer ts.treesMu.Unlock()
+
+ essentialTrees := []btrfsprim.ObjID{
+ btrfsprim.ROOT_TREE_OBJECTID,
+ btrfsprim.UUID_TREE_OBJECTID,
+ }
+
+ for _, treeID := range essentialTrees {
+ treeRoots, ok := roots[treeID]
+ if !ok {
+ continue
+ }
+ tree, err := ts.RebuiltTree(ctx, treeID)
+ if err != nil {
+ dlog.Errorf(ctx, "RebuiltForrest.RebuiltAddRoots: cannot load essential tree %v: %v", treeID, err)
+ return
+ }
+ for _, root := range maps.SortedKeys(treeRoots) {
+ tree.RebuiltAddRoot(ctx, root)
+ }
+ }
+
+ for _, treeID := range maps.SortedKeys(roots) {
+ if slices.Contains(treeID, essentialTrees) {
+ continue
+ }
+ tree, err := ts.RebuiltTree(ctx, treeID)
+ if err != nil {
+ dlog.Errorf(ctx, "RebuiltForrest.RebuiltAddRoots: cannot load non-essential tree %v: %v", treeID, err)
+ continue
+ }
+ for _, root := range maps.SortedKeys(roots[treeID]) {
+ tree.RebuiltAddRoot(ctx, root)
+ }
+ }
+}
+
// btrfs.ReadableFS interface //////////////////////////////////////////////////////////////////////////////////////////
var _ btrfs.ReadableFS = (*RebuiltForrest)(nil)
diff --git a/lib/btrfsutil/rebuilt_tree.go b/lib/btrfsutil/rebuilt_tree.go
index 97308a3..f002ea6 100644
--- a/lib/btrfsutil/rebuilt_tree.go
+++ b/lib/btrfsutil/rebuilt_tree.go
@@ -700,6 +700,10 @@ func (tree *RebuiltTree) RebuiltAddRoot(ctx context.Context, rootNode btrfsvol.L
tree.mu.Lock()
defer tree.mu.Unlock()
+ if tree.Roots.Has(rootNode) {
+ return
+ }
+
ctx = dlog.WithField(ctx, "btrfs.util.rebuilt-tree.add-root", fmt.Sprintf("tree=%v rootNode=%v", tree.ID, rootNode))
dlog.Info(ctx, "adding root...")
diff --git a/scripts/main.sh b/scripts/main.sh
index c9c6f4e..082576a 100755
--- a/scripts/main.sh
+++ b/scripts/main.sh
@@ -78,20 +78,12 @@ run-btrfs-rec $gendir/3.trees.json \
run-btrfs-rec $gendir/4.ls-files.txt \
--mappings=$gendir/2.mappings.json \
- --rebuild \
- inspect ls-files
-run-btrfs-rec $gendir/4.ls-files.v2.txt \
- --mappings=$gendir/2.mappings.json \
--node-list=$gendir/0.nodes.json \
- --rebuild-v2 \
+ --trees=$gendir/3.trees.json \
inspect ls-files
run-btrfs-rec $gendir/4.ls-trees.txt \
--mappings=$gendir/2.mappings.json \
--node-list=$gendir/0.nodes.json \
- inspect ls-trees
-run-btrfs-rec $gendir/4.ls-trees.v2.txt \
- --mappings=$gendir/2.mappings.json \
- --node-list=$gendir/0.nodes.json \
- --rebuild-v2 \
+ --trees=$gendir/3.trees.json \
inspect ls-trees