summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorLuke Shumaker <lukeshu@lukeshu.com>2023-03-10 19:31:50 -0700
committerLuke Shumaker <lukeshu@lukeshu.com>2023-04-17 21:52:25 -0600
commitdc1eddc75a17687ee4d3bc301dd8b2ff253095fe (patch)
tree17ae387fae2f01a9ba94d74cf5f88a64b2c6f7a0
parentee2564cc3164e2c235b3d617a1a4fed2f9d9efc6 (diff)
cmd/btrfs-rec, btrfsutil: Delete OldRebuiltForrest
-rw-r--r--cmd/btrfs-rec/main.go20
-rw-r--r--lib/btrfsutil/old_rebuilt_forrest.go471
-rw-r--r--lib/btrfsutil/rebuilt_forrest.go19
-rwxr-xr-xscripts/main.sh12
4 files changed, 11 insertions, 511 deletions
diff --git a/cmd/btrfs-rec/main.go b/cmd/btrfs-rec/main.go
index ad768de..e167095 100644
--- a/cmd/btrfs-rec/main.go
+++ b/cmd/btrfs-rec/main.go
@@ -49,10 +49,9 @@ var globalFlags struct {
logLevel textui.LogLevelFlag
pvs []string
- mappings string
- nodeList string
- rebuildV1 bool
- rebuildV2 bool
+ mappings string
+ nodeList string
+ rebuild bool
stopProfiling profile.StopFunc
@@ -102,11 +101,8 @@ 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.rebuildV2, "rebuild-v2", false,
- "attempt to rebuild broken btrees when reading (v2)")
+ argparser.PersistentFlags().BoolVar(&globalFlags.rebuild, "rebuild", false,
+ "attempt to rebuild broken btrees when reading")
globalFlags.stopProfiling = profile.AddProfileFlags(argparser.PersistentFlags(), "profile.")
@@ -214,9 +210,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 {
ctx := cmd.Context()
graph, err := btrfsutil.ReadGraph(ctx, fs, nodeList)
@@ -231,7 +225,7 @@ func _runWithReadableFS(wantNodeList bool, runE func(btrfs.ReadableFS, []btrfsvo
}
return func(cmd *cobra.Command, args []string) error {
- if wantNodeList || globalFlags.rebuildV2 {
+ if wantNodeList || globalFlags.rebuild {
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_forrest.go b/lib/btrfsutil/rebuilt_forrest.go
index 79d8beb..0ff45a9 100644
--- a/lib/btrfsutil/rebuilt_forrest.go
+++ b/lib/btrfsutil/rebuilt_forrest.go
@@ -23,23 +23,8 @@ 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.
-//
-// 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:
+// Additionally, it provides some functionality on top of a vanilla
+// btrfs.ReadableFS:
//
// - it provides a RebuiltForrest.RebuiltListRoots() method for
// listing how trees have been repaired.
diff --git a/scripts/main.sh b/scripts/main.sh
index c9c6f4e..4e0596b 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 \
+ --rebuild \
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 \
+ --rebuild \
inspect ls-trees