From c7b6460ee9b3c07c13c973cbc8c8f690560fefc6 Mon Sep 17 00:00:00 2001 From: Luke Shumaker Date: Thu, 2 Mar 2023 16:02:42 -0700 Subject: tree-wide: Drop the old btrfstree.TreeOperator API --- lib/btrfs/btrfstree/btree.go | 53 --------------------- lib/btrfs/btrfstree/btree_forrest.go | 81 ++------------------------------ lib/btrfs/io3_btree.go | 24 ---------- lib/btrfsutil/old_rebuilt_forrest.go | 89 ++++++++---------------------------- 4 files changed, 25 insertions(+), 222 deletions(-) (limited to 'lib') 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] -- cgit v1.2.3-2-g168b