summaryrefslogtreecommitdiff
path: root/lib
diff options
context:
space:
mode:
Diffstat (limited to 'lib')
-rw-r--r--lib/btrfs/btrfstree/btree.go53
-rw-r--r--lib/btrfs/btrfstree/btree_forrest.go81
-rw-r--r--lib/btrfs/io3_btree.go24
-rw-r--r--lib/btrfsutil/old_rebuilt_forrest.go89
4 files changed, 25 insertions, 222 deletions
diff --git a/lib/btrfs/btrfstree/btree.go b/lib/btrfs/btrfstree/btree.go
index cbaa6d0..25259c0 100644
--- a/lib/btrfs/btrfstree/btree.go
+++ b/lib/btrfs/btrfstree/btree.go
@@ -137,59 +137,6 @@ type TreeWalkHandler struct {
BadItem func(Path, Item)
}
-// Compat //////////////////////////////////////////////////////////////////////
-
-// TreeOperator is an interface for performing basic btree operations.
-type TreeOperator interface {
- // TreeWalk walks a tree, triggering callbacks for every node,
- // key-pointer, and item; as well as for any errors encountered.
- //
- // If the tree is valid, then everything is walked in key-order; but
- // if the tree is broken, then ordering is not guaranteed.
- //
- // Canceling the Context causes TreeWalk to return early; no values
- // from the Context are used.
- //
- // The lifecycle of callbacks is:
- //
- // 000 (read superblock) (maybe cbs.BadSuperblock())
- //
- // 001 (read node)
- // 002 cbs.Node() or cbs.BadNode()
- // if interior:
- // for kp in node.items:
- // 003a if cbs.PreKeyPointer == nil || cbs.PreKeyPointer() {
- // 004b (recurse)
- // else:
- // for item in node.items:
- // 003b cbs.Item() or cbs.BadItem()
- TreeWalk(ctx context.Context, treeID btrfsprim.ObjID, errHandle func(*TreeError), cbs TreeWalkHandler)
-
- TreeLookup(treeID btrfsprim.ObjID, key btrfsprim.Key) (Item, error)
- TreeSearch(treeID btrfsprim.ObjID, search TreeSearcher) (Item, error)
-
- // If some items are able to be read, but there is an error reading the
- // full set, then it might return *both* a list of items and an error.
- //
- // If the tree is not found, an error that is ErrNoTree is
- // returned.
- //
- // If no such item is found, an error that is ErrNoItem is
- // returned.
- TreeSearchAll(treeID btrfsprim.ObjID, search TreeSearcher) ([]Item, error)
-}
-
-type TreeError struct {
- Path Path
- Err error
-}
-
-func (e *TreeError) Unwrap() error { return e.Err }
-
-func (e *TreeError) Error() string {
- return fmt.Sprintf("%v: %v", e.Path, e.Err)
-}
-
type NodeSource interface {
Superblock() (*Superblock, error)
AcquireNode(ctx context.Context, addr btrfsvol.LogicalAddr, exp NodeExpectations) (*Node, error)
diff --git a/lib/btrfs/btrfstree/btree_forrest.go b/lib/btrfs/btrfstree/btree_forrest.go
index 4a4a4c0..1a80504 100644
--- a/lib/btrfs/btrfstree/btree_forrest.go
+++ b/lib/btrfs/btrfstree/btree_forrest.go
@@ -40,27 +40,6 @@ type TreeRoot struct {
// LookupTreeRoot, as LookupTreeRoot will not call ForrestLookup for
// ROOT_TREE_OBJECTID; so it will not be an infinite recursion.
func LookupTreeRoot(ctx context.Context, forrest Forrest, sb Superblock, treeID btrfsprim.ObjID) (*TreeRoot, error) {
- return OldLookupTreeRoot(
- ctx,
- func(rootTreeID btrfsprim.ObjID, searcher TreeSearcher) (Item, error) {
- rootTree, err := forrest.ForrestLookup(ctx, rootTreeID)
- if err != nil {
- return Item{}, err
- }
- rootItem, err := rootTree.TreeSearch(ctx, searcher)
- if err != nil {
- return Item{}, err
- }
- return rootItem, nil
- },
- sb,
- treeID,
- )
-}
-
-// OldLookupTreeRoot is a utility function to help with implementing
-// the old 'TreeOperator' interface.
-func OldLookupTreeRoot(_ context.Context, treeSearch func(treeID btrfsprim.ObjID, _ TreeSearcher) (Item, error), sb Superblock, treeID btrfsprim.ObjID) (*TreeRoot, error) {
switch treeID {
case btrfsprim.ROOT_TREE_OBJECTID:
return &TreeRoot{
@@ -91,7 +70,11 @@ func OldLookupTreeRoot(_ context.Context, treeSearch func(treeID btrfsprim.ObjID
Generation: sb.BlockGroupRootGeneration,
}, nil
default:
- rootItem, err := treeSearch(btrfsprim.ROOT_TREE_OBJECTID, SearchRootItem(treeID))
+ rootTree, err := forrest.ForrestLookup(ctx, btrfsprim.ROOT_TREE_OBJECTID)
+ if err != nil {
+ return nil, fmt.Errorf("tree %s: %w", treeID.Format(btrfsprim.ROOT_TREE_OBJECTID), err)
+ }
+ rootItem, err := rootTree.TreeSearch(ctx, SearchRootItem(treeID))
if err != nil {
if errors.Is(err, ErrNoItem) {
err = fmt.Errorf("%w: %s", ErrNoTree, err)
@@ -152,57 +135,3 @@ func (forrest RawForrest) ForrestLookup(ctx context.Context, treeID btrfsprim.Ob
}
return tree, nil
}
-
-// Compat //////////////////////////////////////////////////////////////////////
-
-var _ TreeOperator = RawForrest{}
-
-type TreeOperatorImpl = RawForrest
-
-// TreeWalk implements the 'TreeOperator' interface.
-func (forrest RawForrest) TreeWalk(ctx context.Context, treeID btrfsprim.ObjID, errHandle func(*TreeError), cbs TreeWalkHandler) {
- tree, err := forrest.RawTree(ctx, treeID)
- if err != nil {
- errHandle(&TreeError{Path: Path{PathRoot{TreeID: treeID}}, Err: err})
- return
- }
- tree.TreeWalk(ctx, cbs)
-}
-
-// TreeLookup implements the 'TreeOperator' interface.
-func (forrest RawForrest) TreeLookup(treeID btrfsprim.ObjID, key btrfsprim.Key) (Item, error) {
- ctx := context.TODO()
- tree, err := forrest.RawTree(ctx, treeID)
- if err != nil {
- return Item{}, err
- }
- return tree.TreeLookup(ctx, key)
-}
-
-// TreeSearch implements the 'TreeOperator' interface.
-func (forrest RawForrest) TreeSearch(treeID btrfsprim.ObjID, searcher TreeSearcher) (Item, error) {
- ctx := context.TODO()
- tree, err := forrest.RawTree(ctx, treeID)
- if err != nil {
- return Item{}, err
- }
- return tree.TreeSearch(ctx, searcher)
-}
-
-// TreeSearchAll implements the 'TreeOperator' interface.
-func (forrest RawForrest) TreeSearchAll(treeID btrfsprim.ObjID, searcher TreeSearcher) ([]Item, error) {
- ctx := context.TODO()
- tree, err := forrest.RawTree(ctx, treeID)
- if err != nil {
- return nil, err
- }
-
- var ret []Item
- err = tree.TreeSubrange(ctx, 1, searcher, func(item Item) bool {
- item.Body = item.Body.CloneItem()
- ret = append(ret, item)
- return true
- })
-
- return ret, err
-}
diff --git a/lib/btrfs/io3_btree.go b/lib/btrfs/io3_btree.go
index 59e4c1d..01797df 100644
--- a/lib/btrfs/io3_btree.go
+++ b/lib/btrfs/io3_btree.go
@@ -89,30 +89,6 @@ func (fs *FS) ForrestLookup(ctx context.Context, treeID btrfsprim.ObjID) (btrfst
var _ btrfstree.Forrest = (*FS)(nil)
-// btrfstree.TreeOperator //////////////////////////////////////////////////////
-
-// TreeWalk implements btrfstree.TreeOperator.
-func (fs *FS) TreeWalk(ctx context.Context, treeID btrfsprim.ObjID, errHandle func(*btrfstree.TreeError), cbs btrfstree.TreeWalkHandler) {
- btrfstree.TreeOperatorImpl{NodeSource: fs}.TreeWalk(ctx, treeID, errHandle, cbs)
-}
-
-// TreeLookup implements btrfstree.TreeOperator.
-func (fs *FS) TreeLookup(treeID btrfsprim.ObjID, key btrfsprim.Key) (btrfstree.Item, error) {
- return btrfstree.TreeOperatorImpl{NodeSource: fs}.TreeLookup(treeID, key)
-}
-
-// TreeSearch implements btrfstree.TreeOperator.
-func (fs *FS) TreeSearch(treeID btrfsprim.ObjID, searcher btrfstree.TreeSearcher) (btrfstree.Item, error) {
- return btrfstree.TreeOperatorImpl{NodeSource: fs}.TreeSearch(treeID, searcher)
-}
-
-// TreeSearchAll implements btrfstree.TreeOperator.
-func (fs *FS) TreeSearchAll(treeID btrfsprim.ObjID, searcher btrfstree.TreeSearcher) ([]btrfstree.Item, error) {
- return btrfstree.TreeOperatorImpl{NodeSource: fs}.TreeSearchAll(treeID, searcher)
-}
-
-var _ btrfstree.TreeOperator = (*FS)(nil)
-
// ReadableFS //////////////////////////////////////////////////////////////////
type ReadableFS interface {
diff --git a/lib/btrfsutil/old_rebuilt_forrest.go b/lib/btrfsutil/old_rebuilt_forrest.go
index ae63001..58333df 100644
--- a/lib/btrfsutil/old_rebuilt_forrest.go
+++ b/lib/btrfsutil/old_rebuilt_forrest.go
@@ -85,7 +85,6 @@ func newOldRebuiltTree() oldRebuiltTree {
}
type OldRebuiltForrest struct {
- ctx context.Context //nolint:containedctx // don't have an option while keeping the same API
inner *btrfs.FS
// btrfsprim.ROOT_TREE_OBJECTID
@@ -96,32 +95,27 @@ type OldRebuiltForrest struct {
trees map[btrfsprim.ObjID]oldRebuiltTree
}
-var (
- _ btrfstree.TreeOperator = (*OldRebuiltForrest)(nil)
- _ btrfs.ReadableFS = (*OldRebuiltForrest)(nil)
-)
+var _ btrfs.ReadableFS = (*OldRebuiltForrest)(nil)
// NewOldRebuiltForrest wraps a *btrfs.FS to support looking up
// information from broken trees.
//
-// Of the btrfstree.TreeOperator methods:
+// Of the btrfstree.Tree methods:
//
-// - TreeWalk works on broken trees
-// - TreeLookup relies on the tree being properly ordered (which a
+// - 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).
-// - 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.
+// - TreeLookup relies on the tree being properly ordered (which a
+// broken tree might not be).
//
-// NewOldRebuiltForrest 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
+// 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(ctx context.Context, inner *btrfs.FS) *OldRebuiltForrest {
+func NewOldRebuiltForrest(inner *btrfs.FS) *OldRebuiltForrest {
return &OldRebuiltForrest{
- ctx: ctx,
inner: inner,
}
}
@@ -251,8 +245,8 @@ func (tree oldRebuiltTree) addErrs(fn func(btrfsprim.Key, uint32) int, err error
return errs
}
-func (bt *OldRebuiltForrest) readNode(nodeInfo nodeInfo) *btrfstree.Node {
- node, err := bt.inner.AcquireNode(bt.ctx, nodeInfo.LAddr, btrfstree.NodeExpectations{
+func (bt *OldRebuiltForrest) readNode(ctx context.Context, nodeInfo nodeInfo) *btrfstree.Node {
+ node, err := bt.inner.AcquireNode(ctx, nodeInfo.LAddr, btrfstree.NodeExpectations{
LAddr: containers.OptionalValue(nodeInfo.LAddr),
Level: containers.OptionalValue(nodeInfo.Level),
Generation: containers.OptionalValue(nodeInfo.Generation),
@@ -274,23 +268,13 @@ func (bt *OldRebuiltForrest) readNode(nodeInfo nodeInfo) *btrfstree.Node {
return node
}
-// TreeLookup implements btrfstree.TreeOperator.
-func (bt *OldRebuiltForrest) TreeLookup(treeID btrfsprim.ObjID, key btrfsprim.Key) (btrfstree.Item, error) {
- return bt.RebuiltTree(bt.ctx, treeID).TreeLookup(bt.ctx, key)
-}
-
// 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.TreeOperator.
-func (bt *OldRebuiltForrest) TreeSearch(treeID btrfsprim.ObjID, searcher btrfstree.TreeSearcher) (btrfstree.Item, error) {
- return bt.RebuiltTree(bt.ctx, treeID).TreeSearch(bt.ctx, searcher)
-}
-
// TreeSearch implements btrfstree.Tree.
-func (tree oldRebuiltTree) TreeSearch(_ context.Context, searcher btrfstree.TreeSearcher) (btrfstree.Item, error) {
+func (tree oldRebuiltTree) TreeSearch(ctx context.Context, searcher btrfstree.TreeSearcher) (btrfstree.Item, error) {
if tree.RootErr != nil {
return btrfstree.Item{}, tree.RootErr
}
@@ -302,7 +286,7 @@ func (tree oldRebuiltTree) TreeSearch(_ context.Context, searcher btrfstree.Tree
return btrfstree.Item{}, fmt.Errorf("item with %s: %w", searcher, tree.addErrs(searcher.Search, btrfstree.ErrNoItem))
}
- node := tree.forrest.readNode(indexItem.Value.Node)
+ node := tree.forrest.readNode(ctx, indexItem.Value.Node)
defer tree.forrest.inner.ReleaseNode(node)
item := node.BodyLeaf[indexItem.Value.Slot]
@@ -314,7 +298,7 @@ func (tree oldRebuiltTree) TreeSearch(_ context.Context, searcher btrfstree.Tree
}
// TreeRange implements btrfstree.Tree.
-func (tree oldRebuiltTree) TreeRange(_ context.Context, handleFn func(btrfstree.Item) bool) error {
+func (tree oldRebuiltTree) TreeRange(ctx context.Context, handleFn func(btrfstree.Item) bool) error {
if tree.RootErr != nil {
return tree.RootErr
}
@@ -324,7 +308,7 @@ func (tree oldRebuiltTree) TreeRange(_ context.Context, handleFn func(btrfstree.
func(rbnode *containers.RBNode[oldRebuiltTreeValue]) bool {
if node == nil || node.Head.Addr != rbnode.Value.Node.LAddr {
tree.forrest.inner.ReleaseNode(node)
- node = tree.forrest.readNode(rbnode.Value.Node)
+ node = tree.forrest.readNode(ctx, rbnode.Value.Node)
}
return handleFn(node.BodyLeaf[rbnode.Value.Slot])
})
@@ -333,25 +317,8 @@ func (tree oldRebuiltTree) TreeRange(_ context.Context, handleFn func(btrfstree.
return tree.addErrs(func(btrfsprim.Key, uint32) int { return 0 }, nil)
}
-// TreeSearchAll implements btrfstree.TreeOperator.
-func (bt *OldRebuiltForrest) TreeSearchAll(treeID btrfsprim.ObjID, searcher btrfstree.TreeSearcher) ([]btrfstree.Item, error) {
- tree := bt.RebuiltTree(bt.ctx, treeID)
- if tree.RootErr != nil {
- return nil, tree.RootErr
- }
-
- var ret []btrfstree.Item
- err := tree.TreeSubrange(bt.ctx, 1, searcher, func(item btrfstree.Item) bool {
- item.Body = item.Body.CloneItem()
- ret = append(ret, item)
- return true
- })
-
- return ret, err
-}
-
// TreeSubrange implements btrfstree.Tree.
-func (tree oldRebuiltTree) TreeSubrange(_ context.Context, min int, searcher btrfstree.TreeSearcher, handleFn func(btrfstree.Item) bool) error {
+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(
@@ -362,7 +329,7 @@ func (tree oldRebuiltTree) TreeSubrange(_ context.Context, min int, searcher btr
cnt++
if node == nil || node.Head.Addr != rbNode.Value.Node.LAddr {
tree.forrest.inner.ReleaseNode(node)
- node = tree.forrest.readNode(rbNode.Value.Node)
+ node = tree.forrest.readNode(ctx, rbNode.Value.Node)
}
return handleFn(node.BodyLeaf[rbNode.Value.Slot])
})
@@ -379,20 +346,6 @@ func (tree oldRebuiltTree) TreeSubrange(_ context.Context, min int, searcher btr
return err
}
-// TreeWalk implements btrfstree.TreeOperator. It doesn't actually
-// visit nodes or keypointers (just items).
-func (bt *OldRebuiltForrest) TreeWalk(ctx context.Context, treeID btrfsprim.ObjID, errHandle func(*btrfstree.TreeError), cbs btrfstree.TreeWalkHandler) {
- tree := bt.RebuiltTree(ctx, treeID)
- if tree.RootErr != nil {
- errHandle(&btrfstree.TreeError{
- Path: btrfstree.Path{btrfstree.PathRoot{TreeID: treeID}},
- Err: tree.RootErr,
- })
- return
- }
- tree.TreeWalk(ctx, cbs)
-}
-
// TreeWalk implements btrfstree.Tree. It doesn't actually visit
// nodes or keypointers (just items).
func (tree oldRebuiltTree) TreeWalk(ctx context.Context, cbs btrfstree.TreeWalkHandler) {
@@ -404,12 +357,10 @@ func (tree oldRebuiltTree) TreeWalk(ctx context.Context, cbs btrfstree.TreeWalkH
if ctx.Err() != nil {
return false
}
- if tree.forrest.ctx.Err() != nil {
- return false
- }
+
if node == nil || node.Head.Addr != indexItem.Value.Node.LAddr {
tree.forrest.inner.ReleaseNode(node)
- node = tree.forrest.readNode(indexItem.Value.Node)
+ node = tree.forrest.readNode(ctx, indexItem.Value.Node)
}
item := node.BodyLeaf[indexItem.Value.Slot]
generated by cgit v1.2.3-2-g168b (git 2.25.1) at 2024-08-19 23:46:29 +0000