From 0d6880131e90b43e03e0878dfc2ea2b6f0f2291e Mon Sep 17 00:00:00 2001 From: Luke Shumaker Date: Mon, 13 Mar 2023 18:49:47 -0600 Subject: btrfstree: Have LookupTreeRoot take a Context --- cmd/btrfs-rec/inspect/rebuildtrees/scan.go | 2 +- lib/btrfs/btrfstree/btree_forrest.go | 3 ++- lib/btrfs/btrfstree/btree_tree.go | 8 +++++--- lib/btrfsutil/graph.go | 14 +++++++------- lib/btrfsutil/old_rebuilt_forrest.go | 2 +- 5 files changed, 16 insertions(+), 13 deletions(-) diff --git a/cmd/btrfs-rec/inspect/rebuildtrees/scan.go b/cmd/btrfs-rec/inspect/rebuildtrees/scan.go index ada9f6f..3339270 100644 --- a/cmd/btrfs-rec/inspect/rebuildtrees/scan.go +++ b/cmd/btrfs-rec/inspect/rebuildtrees/scan.go @@ -59,7 +59,7 @@ func ScanDevices(ctx context.Context, fs *btrfs.FS, nodeList []btrfsvol.LogicalA ret := ScanDevicesResult{ Superblock: *sb, - Graph: btrfsutil.NewGraph(*sb), + Graph: btrfsutil.NewGraph(ctx, *sb), Flags: make(map[btrfsutil.ItemPtr]FlagsAndErr), Names: make(map[btrfsutil.ItemPtr][]byte), diff --git a/lib/btrfs/btrfstree/btree_forrest.go b/lib/btrfs/btrfstree/btree_forrest.go index 0f46d42..d4317d6 100644 --- a/lib/btrfs/btrfstree/btree_forrest.go +++ b/lib/btrfs/btrfstree/btree_forrest.go @@ -5,6 +5,7 @@ package btrfstree import ( + "context" "errors" "fmt" @@ -24,7 +25,7 @@ type TreeRoot struct { // LookupTreeRoot is a utility function to help with implementing the // 'TreeOperator' interface. -func LookupTreeRoot(fs TreeOperator, sb Superblock, treeID btrfsprim.ObjID) (*TreeRoot, error) { +func LookupTreeRoot(_ context.Context, fs TreeOperator, sb Superblock, treeID btrfsprim.ObjID) (*TreeRoot, error) { switch treeID { case btrfsprim.ROOT_TREE_OBJECTID: return &TreeRoot{ diff --git a/lib/btrfs/btrfstree/btree_tree.go b/lib/btrfs/btrfstree/btree_tree.go index 459f481..a34946e 100644 --- a/lib/btrfs/btrfstree/btree_tree.go +++ b/lib/btrfs/btrfstree/btree_tree.go @@ -28,7 +28,7 @@ func (fs TreeOperatorImpl) TreeWalk(ctx context.Context, treeID btrfsprim.ObjID, if err != nil { errHandle(&TreeError{Path: Path{{FromTree: treeID, ToMaxKey: btrfsprim.MaxKey}}, Err: err}) } - rootInfo, err := LookupTreeRoot(fs, *sb, treeID) + rootInfo, err := LookupTreeRoot(ctx, fs, *sb, treeID) if err != nil { errHandle(&TreeError{Path: Path{{FromTree: treeID, ToMaxKey: btrfsprim.MaxKey}}, Err: err}) return @@ -405,11 +405,12 @@ func (fs TreeOperatorImpl) next(path Path, node *Node) (Path, *Node, error) { // TreeSearch implements the 'TreeOperator' interface. func (fs TreeOperatorImpl) TreeSearch(treeID btrfsprim.ObjID, searcher TreeSearcher) (Item, error) { + ctx := context.TODO() sb, err := fs.Superblock() if err != nil { return Item{}, err } - rootInfo, err := LookupTreeRoot(fs, *sb, treeID) + rootInfo, err := LookupTreeRoot(ctx, fs, *sb, treeID) if err != nil { return Item{}, err } @@ -430,11 +431,12 @@ func (fs TreeOperatorImpl) TreeLookup(treeID btrfsprim.ObjID, key btrfsprim.Key) // TreeSearchAll implements the 'TreeOperator' interface. func (fs TreeOperatorImpl) TreeSearchAll(treeID btrfsprim.ObjID, searcher TreeSearcher) ([]Item, error) { + ctx := context.TODO() sb, err := fs.Superblock() if err != nil { return nil, err } - rootInfo, err := LookupTreeRoot(fs, *sb, treeID) + rootInfo, err := LookupTreeRoot(ctx, fs, *sb, treeID) if err != nil { return nil, err } diff --git a/lib/btrfsutil/graph.go b/lib/btrfsutil/graph.go index 35848de..39e1cf2 100644 --- a/lib/btrfsutil/graph.go +++ b/lib/btrfsutil/graph.go @@ -111,8 +111,8 @@ func (g Graph) insertEdge(ptr *GraphEdge) { 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) +func (g Graph) insertTreeRoot(ctx context.Context, sb btrfstree.Superblock, treeID btrfsprim.ObjID) { + treeInfo, err := btrfstree.LookupTreeRoot(ctx, nil, sb, treeID) if err != nil { // This shouldn't ever happen for treeIDs that are // mentioned directly in the superblock; which are the @@ -131,7 +131,7 @@ func (g Graph) insertTreeRoot(sb btrfstree.Superblock, treeID btrfsprim.ObjID) { }) } -func NewGraph(sb btrfstree.Superblock) Graph { +func NewGraph(ctx context.Context, sb btrfstree.Superblock) Graph { g := Graph{ Nodes: make(map[btrfsvol.LogicalAddr]GraphNode), BadNodes: make(map[btrfsvol.LogicalAddr]error), @@ -141,10 +141,10 @@ func NewGraph(sb btrfstree.Superblock) Graph { // 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) + g.insertTreeRoot(ctx, sb, btrfsprim.ROOT_TREE_OBJECTID) + g.insertTreeRoot(ctx, sb, btrfsprim.CHUNK_TREE_OBJECTID) + g.insertTreeRoot(ctx, sb, btrfsprim.TREE_LOG_OBJECTID) + g.insertTreeRoot(ctx, sb, btrfsprim.BLOCK_GROUP_TREE_OBJECTID) return g } diff --git a/lib/btrfsutil/old_rebuilt_forrest.go b/lib/btrfsutil/old_rebuilt_forrest.go index abe3329..8ae7149 100644 --- a/lib/btrfsutil/old_rebuilt_forrest.go +++ b/lib/btrfsutil/old_rebuilt_forrest.go @@ -153,7 +153,7 @@ func (bt *OldRebuiltForrest) rawTreeWalk(treeID btrfsprim.ObjID, cacheEntry *old cacheEntry.RootErr = err return } - root, err := btrfstree.LookupTreeRoot(bt, *sb, treeID) + root, err := btrfstree.LookupTreeRoot(bt.ctx, bt, *sb, treeID) if err != nil { cacheEntry.RootErr = err return -- cgit v1.1-4-g5e80 From e5bd082182f410bb46aa7653e8af0b440ec3632b Mon Sep 17 00:00:00 2001 From: Luke Shumaker Date: Mon, 13 Mar 2023 16:25:33 -0600 Subject: btrfstree: btree.go: Move TreeWalkHandler up in the file --- lib/btrfs/btrfstree/btree.go | 38 +++++++++++++++++++------------------- 1 file changed, 19 insertions(+), 19 deletions(-) diff --git a/lib/btrfs/btrfstree/btree.go b/lib/btrfs/btrfstree/btree.go index e91fcc1..9713295 100644 --- a/lib/btrfs/btrfstree/btree.go +++ b/lib/btrfs/btrfstree/btree.go @@ -22,6 +22,25 @@ type TreeSearcher interface { Search(key btrfsprim.Key, size uint32) int } +type TreeWalkHandler struct { + // Callbacks for entire nodes. + // + // If any of these return an error that is io/fs.SkipDir, the + // node immediately stops getting processed; if PreNode, Node, + // or BadNode return io/fs.SkipDir then key pointers and items + // within the node are not processed. + PreNode func(Path) error + Node func(Path, *Node) error + BadNode func(Path, *Node, error) error + PostNode func(Path, *Node) error + // Callbacks for items on interior nodes + PreKeyPointer func(Path, KeyPointer) error + PostKeyPointer func(Path, KeyPointer) error + // Callbacks for items on leaf nodes + Item func(Path, Item) error + BadItem func(Path, Item) error +} + // TreeOperator is an interface for performing basic btree operations. type TreeOperator interface { // TreeWalk walks a tree, triggering callbacks for every node, @@ -62,25 +81,6 @@ type TreeOperator interface { TreeSearchAll(treeID btrfsprim.ObjID, search TreeSearcher) ([]Item, error) } -type TreeWalkHandler struct { - // Callbacks for entire nodes. - // - // If any of these return an error that is io/fs.SkipDir, the - // node immediately stops getting processed; if PreNode, Node, - // or BadNode return io/fs.SkipDir then key pointers and items - // within the node are not processed. - PreNode func(Path) error - Node func(Path, *Node) error - BadNode func(Path, *Node, error) error - PostNode func(Path, *Node) error - // Callbacks for items on interior nodes - PreKeyPointer func(Path, KeyPointer) error - PostKeyPointer func(Path, KeyPointer) error - // Callbacks for items on leaf nodes - Item func(Path, Item) error - BadItem func(Path, Item) error -} - type TreeError struct { Path Path Err error -- cgit v1.1-4-g5e80 From c4597bbacc76eb5ddea4d3a2a062353895c90fbe Mon Sep 17 00:00:00 2001 From: Luke Shumaker Date: Mon, 13 Mar 2023 23:58:04 -0600 Subject: btrfstree: TreeRoot: Rename the member from TreeID to just ID --- lib/btrfs/btrfstree/btree_forrest.go | 12 ++++++------ lib/btrfs/btrfstree/btree_tree.go | 4 ++-- lib/btrfsutil/old_rebuilt_forrest.go | 2 +- 3 files changed, 9 insertions(+), 9 deletions(-) diff --git a/lib/btrfs/btrfstree/btree_forrest.go b/lib/btrfs/btrfstree/btree_forrest.go index d4317d6..acbd3f9 100644 --- a/lib/btrfs/btrfstree/btree_forrest.go +++ b/lib/btrfs/btrfstree/btree_forrest.go @@ -17,7 +17,7 @@ import ( // A TreeRoot is more-or-less a btrfsitem.Root, but simpler; returned by // LookupTreeRoot. type TreeRoot struct { - TreeID btrfsprim.ObjID + ID btrfsprim.ObjID RootNode btrfsvol.LogicalAddr Level uint8 Generation btrfsprim.Generation @@ -29,28 +29,28 @@ func LookupTreeRoot(_ context.Context, fs TreeOperator, sb Superblock, treeID bt switch treeID { case btrfsprim.ROOT_TREE_OBJECTID: return &TreeRoot{ - TreeID: treeID, + ID: treeID, RootNode: sb.RootTree, Level: sb.RootLevel, Generation: sb.Generation, // XXX: same generation as LOG_TREE? }, nil case btrfsprim.CHUNK_TREE_OBJECTID: return &TreeRoot{ - TreeID: treeID, + ID: treeID, RootNode: sb.ChunkTree, Level: sb.ChunkLevel, Generation: sb.ChunkRootGeneration, }, nil case btrfsprim.TREE_LOG_OBJECTID: return &TreeRoot{ - TreeID: treeID, + ID: treeID, RootNode: sb.LogTree, Level: sb.LogLevel, Generation: sb.Generation, // XXX: same generation as ROOT_TREE? }, nil case btrfsprim.BLOCK_GROUP_TREE_OBJECTID: return &TreeRoot{ - TreeID: treeID, + ID: treeID, RootNode: sb.BlockGroupRoot, Level: sb.BlockGroupRootLevel, Generation: sb.BlockGroupRootGeneration, @@ -66,7 +66,7 @@ func LookupTreeRoot(_ context.Context, fs TreeOperator, sb Superblock, treeID bt switch rootItemBody := rootItem.Body.(type) { case *btrfsitem.Root: return &TreeRoot{ - TreeID: treeID, + ID: treeID, RootNode: rootItemBody.ByteNr, Level: rootItemBody.Level, Generation: rootItemBody.Generation, diff --git a/lib/btrfs/btrfstree/btree_tree.go b/lib/btrfs/btrfstree/btree_tree.go index a34946e..ac7784e 100644 --- a/lib/btrfs/btrfstree/btree_tree.go +++ b/lib/btrfs/btrfstree/btree_tree.go @@ -40,7 +40,7 @@ func (fs TreeOperatorImpl) TreeWalk(ctx context.Context, treeID btrfsprim.ObjID, // 'TreeOperator' interface. func (fs TreeOperatorImpl) RawTreeWalk(ctx context.Context, rootInfo TreeRoot, errHandle func(*TreeError), cbs TreeWalkHandler) { path := Path{{ - FromTree: rootInfo.TreeID, + FromTree: rootInfo.ID, FromItemSlot: -1, ToNodeAddr: rootInfo.RootNode, ToNodeGeneration: rootInfo.Generation, @@ -169,7 +169,7 @@ func (fs TreeOperatorImpl) treeWalk(ctx context.Context, path Path, errHandle fu func (fs TreeOperatorImpl) treeSearch(treeRoot TreeRoot, fn func(btrfsprim.Key, uint32) int) (Path, *Node, error) { path := Path{{ - FromTree: treeRoot.TreeID, + FromTree: treeRoot.ID, FromItemSlot: -1, ToNodeAddr: treeRoot.RootNode, ToNodeGeneration: treeRoot.Generation, diff --git a/lib/btrfsutil/old_rebuilt_forrest.go b/lib/btrfsutil/old_rebuilt_forrest.go index 8ae7149..ace79e9 100644 --- a/lib/btrfsutil/old_rebuilt_forrest.go +++ b/lib/btrfsutil/old_rebuilt_forrest.go @@ -203,7 +203,7 @@ func (bt *OldRebuiltForrest) rawTreeWalk(treeID btrfsprim.ObjID, cacheEntry *old // 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)) + panic(fmt.Errorf("dup key=%v in tree=%v", item.Key, treeID)) } cacheEntry.Items.Insert(oldRebuiltTreeValue{ Key: item.Key, -- cgit v1.1-4-g5e80 From 8d3cd03a0339f045ea58878eff6a2c0ced27955e Mon Sep 17 00:00:00 2001 From: Luke Shumaker Date: Sat, 18 Mar 2023 15:18:29 -0400 Subject: btrfsutil: OldRebuiltForrest: Simplify the TreeSearchAll implementation --- lib/btrfsutil/old_rebuilt_forrest.go | 34 ++++++++++++++++------------------ 1 file changed, 16 insertions(+), 18 deletions(-) diff --git a/lib/btrfsutil/old_rebuilt_forrest.go b/lib/btrfsutil/old_rebuilt_forrest.go index ace79e9..0887bf9 100644 --- a/lib/btrfsutil/old_rebuilt_forrest.go +++ b/lib/btrfsutil/old_rebuilt_forrest.go @@ -297,35 +297,33 @@ func (bt *OldRebuiltForrest) TreeSearchAll(treeID btrfsprim.ObjID, searcher btrf return nil, tree.RootErr } - var indexItems []oldRebuiltTreeValue + var ret []btrfstree.Item + var node *btrfstree.Node tree.Items.Subrange( func(indexItem oldRebuiltTreeValue) int { return searcher.Search(indexItem.Key, indexItem.ItemSize) }, - func(node *containers.RBNode[oldRebuiltTreeValue]) bool { - indexItems = append(indexItems, node.Value) + func(rbNode *containers.RBNode[oldRebuiltTreeValue]) bool { + if node == nil || node.Head.Addr != rbNode.Value.Node.LAddr { + node.Free() + node = bt.readNode(rbNode.Value.Node) + } + item := node.BodyLeaf[rbNode.Value.Slot] + item.Body = item.Body.CloneItem() + ret = append(ret, item) return true }) - if len(indexItems) == 0 { - return nil, fmt.Errorf("items with %s: %w", searcher, tree.addErrs(searcher.Search, btrfstree.ErrNoItem)) - } - - ret := make([]btrfstree.Item, len(indexItems)) - var node *btrfstree.Node - for i, indexItem := range indexItems { - if node == nil || node.Head.Addr != indexItem.Node.LAddr { - node.Free() - node = bt.readNode(indexItem.Node) - } - ret[i] = node.BodyLeaf[indexItem.Slot] - ret[i].Body = ret[i].Body.CloneItem() - } node.Free() - err := tree.addErrs(searcher.Search, nil) + var err error + if len(ret) == 0 { + err = btrfstree.ErrNoItem + } + err = tree.addErrs(searcher.Search, err) if err != nil { err = fmt.Errorf("items with %s: %w", searcher, err) } + return ret, err } -- cgit v1.1-4-g5e80 From c2d3878332b3e8853257b6ee5712a5a995987387 Mon Sep 17 00:00:00 2001 From: Luke Shumaker Date: Thu, 2 Mar 2023 23:33:49 -0700 Subject: btrfsutil: OldRebuiltForrest: Have .RebuiltTree take a Context --- lib/btrfsutil/old_rebuilt_forrest.go | 20 ++++++++++---------- 1 file changed, 10 insertions(+), 10 deletions(-) diff --git a/lib/btrfsutil/old_rebuilt_forrest.go b/lib/btrfsutil/old_rebuilt_forrest.go index 0887bf9..0d6adc6 100644 --- a/lib/btrfsutil/old_rebuilt_forrest.go +++ b/lib/btrfsutil/old_rebuilt_forrest.go @@ -114,7 +114,7 @@ func NewOldRebuiltForrest(ctx context.Context, inner *btrfs.FS) *OldRebuiltForre } } -func (bt *OldRebuiltForrest) RebuiltTree(treeID btrfsprim.ObjID) oldRebuiltTree { +func (bt *OldRebuiltForrest) RebuiltTree(ctx context.Context, treeID btrfsprim.ObjID) oldRebuiltTree { if treeID == btrfsprim.ROOT_TREE_OBJECTID { bt.rootTreeMu.Lock() defer bt.rootTreeMu.Unlock() @@ -133,9 +133,9 @@ func (bt *OldRebuiltForrest) RebuiltTree(treeID btrfsprim.ObjID) oldRebuiltTree } cacheEntry := newOldRebuiltTree() - dlog.Infof(bt.ctx, "indexing tree %v...", treeID) - bt.rawTreeWalk(treeID, &cacheEntry) - dlog.Infof(bt.ctx, "... done indexing tree %v", 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 @@ -147,13 +147,13 @@ func (bt *OldRebuiltForrest) RebuiltTree(treeID btrfsprim.ObjID) oldRebuiltTree func discardOK[T any](x T, _ bool) T { return x } -func (bt *OldRebuiltForrest) rawTreeWalk(treeID btrfsprim.ObjID, cacheEntry *oldRebuiltTree) { +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(bt.ctx, bt, *sb, treeID) + root, err := btrfstree.LookupTreeRoot(ctx, bt, *sb, treeID) if err != nil { cacheEntry.RootErr = err return @@ -216,7 +216,7 @@ func (bt *OldRebuiltForrest) rawTreeWalk(treeID btrfsprim.ObjID, cacheEntry *old }, } - btrfstree.TreeOperatorImpl{NodeSource: bt.inner}.RawTreeWalk(bt.ctx, *root, errHandle, cbs) + btrfstree.TreeOperatorImpl{NodeSource: bt.inner}.RawTreeWalk(ctx, *root, errHandle, cbs) } func (bt *OldRebuiltForrest) TreeLookup(treeID btrfsprim.ObjID, key btrfsprim.Key) (btrfstree.Item, error) { @@ -268,7 +268,7 @@ func (bt *OldRebuiltForrest) readNode(nodeInfo nodeInfo) *btrfstree.Node { } func (bt *OldRebuiltForrest) TreeSearch(treeID btrfsprim.ObjID, searcher btrfstree.TreeSearcher) (btrfstree.Item, error) { - tree := bt.RebuiltTree(treeID) + tree := bt.RebuiltTree(bt.ctx, treeID) if tree.RootErr != nil { return btrfstree.Item{}, tree.RootErr } @@ -292,7 +292,7 @@ func (bt *OldRebuiltForrest) TreeSearch(treeID btrfsprim.ObjID, searcher btrfstr } func (bt *OldRebuiltForrest) TreeSearchAll(treeID btrfsprim.ObjID, searcher btrfstree.TreeSearcher) ([]btrfstree.Item, error) { - tree := bt.RebuiltTree(treeID) + tree := bt.RebuiltTree(bt.ctx, treeID) if tree.RootErr != nil { return nil, tree.RootErr } @@ -328,7 +328,7 @@ func (bt *OldRebuiltForrest) TreeSearchAll(treeID btrfsprim.ObjID, searcher btrf } func (bt *OldRebuiltForrest) TreeWalk(ctx context.Context, treeID btrfsprim.ObjID, errHandle func(*btrfstree.TreeError), cbs btrfstree.TreeWalkHandler) { - tree := bt.RebuiltTree(treeID) + tree := bt.RebuiltTree(ctx, treeID) if tree.RootErr != nil { errHandle(&btrfstree.TreeError{ Path: btrfstree.Path{{ -- cgit v1.1-4-g5e80 From ae15854423fd855ced22c9cb6c9ec94c83223d30 Mon Sep 17 00:00:00 2001 From: Luke Shumaker Date: Sat, 18 Mar 2023 00:38:16 -0400 Subject: btrfsutil: OldRebuiltForrest: Move .TreeLookup() down within the file --- lib/btrfsutil/old_rebuilt_forrest.go | 8 ++++---- 1 file changed, 4 insertions(+), 4 deletions(-) diff --git a/lib/btrfsutil/old_rebuilt_forrest.go b/lib/btrfsutil/old_rebuilt_forrest.go index 0d6adc6..fed3dd4 100644 --- a/lib/btrfsutil/old_rebuilt_forrest.go +++ b/lib/btrfsutil/old_rebuilt_forrest.go @@ -219,10 +219,6 @@ func (bt *OldRebuiltForrest) rawTreeWalk(ctx context.Context, treeID btrfsprim.O btrfstree.TreeOperatorImpl{NodeSource: bt.inner}.RawTreeWalk(ctx, *root, errHandle, cbs) } -func (bt *OldRebuiltForrest) TreeLookup(treeID btrfsprim.ObjID, key btrfsprim.Key) (btrfstree.Item, error) { - return bt.TreeSearch(treeID, btrfstree.SearchExactKey(key)) -} - func (tree oldRebuiltTree) addErrs(fn func(btrfsprim.Key, uint32) int, err error) error { var errs derror.MultiError tree.Errors.Subrange( @@ -267,6 +263,10 @@ func (bt *OldRebuiltForrest) readNode(nodeInfo nodeInfo) *btrfstree.Node { return node } +func (bt *OldRebuiltForrest) TreeLookup(treeID btrfsprim.ObjID, key btrfsprim.Key) (btrfstree.Item, error) { + return bt.TreeSearch(treeID, btrfstree.SearchExactKey(key)) +} + func (bt *OldRebuiltForrest) TreeSearch(treeID btrfsprim.ObjID, searcher btrfstree.TreeSearcher) (btrfstree.Item, error) { tree := bt.RebuiltTree(bt.ctx, treeID) if tree.RootErr != nil { -- cgit v1.1-4-g5e80 From cbb0ec1c505898bdd7062370351311f8a3da8fd8 Mon Sep 17 00:00:00 2001 From: Luke Shumaker Date: Thu, 2 Mar 2023 23:33:49 -0700 Subject: btrfsutil: OldRebuiltForrest: Add some doc comments --- lib/btrfsutil/old_rebuilt_forrest.go | 7 +++++++ 1 file changed, 7 insertions(+) diff --git a/lib/btrfsutil/old_rebuilt_forrest.go b/lib/btrfsutil/old_rebuilt_forrest.go index fed3dd4..4573e28 100644 --- a/lib/btrfsutil/old_rebuilt_forrest.go +++ b/lib/btrfsutil/old_rebuilt_forrest.go @@ -114,6 +114,8 @@ func NewOldRebuiltForrest(ctx context.Context, inner *btrfs.FS) *OldRebuiltForre } } +// RebuiltTree returns a handle for an individual tree. 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() @@ -263,10 +265,12 @@ 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.TreeSearch(treeID, btrfstree.SearchExactKey(key)) } +// TreeSearch implements btrfstree.TreeOperator. func (bt *OldRebuiltForrest) TreeSearch(treeID btrfsprim.ObjID, searcher btrfstree.TreeSearcher) (btrfstree.Item, error) { tree := bt.RebuiltTree(bt.ctx, treeID) if tree.RootErr != nil { @@ -291,6 +295,7 @@ func (bt *OldRebuiltForrest) TreeSearch(treeID btrfsprim.ObjID, searcher btrfstr return item, 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 { @@ -380,10 +385,12 @@ func (bt *OldRebuiltForrest) TreeWalk(ctx context.Context, treeID btrfsprim.ObjI node.Free() } +// Superblock implements btrfs.ReadableFS. func (bt *OldRebuiltForrest) Superblock() (*btrfstree.Superblock, error) { return bt.inner.Superblock() } +// ReadAt implements diskio.ReaderAt (and btrfs.ReadableFS). func (bt *OldRebuiltForrest) ReadAt(p []byte, off btrfsvol.LogicalAddr) (int, error) { return bt.inner.ReadAt(p, off) } -- cgit v1.1-4-g5e80 From 55f74940d5a4a7ea09c1be9dec0a3fc39e88434c Mon Sep 17 00:00:00 2001 From: Luke Shumaker Date: Sat, 18 Mar 2023 00:49:01 -0400 Subject: btrfsutil: OldRebuiltForrest: Move the implementations of methods to the trees --- lib/btrfsutil/old_rebuilt_forrest.go | 54 ++++++++++++++++++++++++++---------- 1 file changed, 40 insertions(+), 14 deletions(-) diff --git a/lib/btrfsutil/old_rebuilt_forrest.go b/lib/btrfsutil/old_rebuilt_forrest.go index 4573e28..ea9ecdc 100644 --- a/lib/btrfsutil/old_rebuilt_forrest.go +++ b/lib/btrfsutil/old_rebuilt_forrest.go @@ -20,6 +20,10 @@ import ( ) type oldRebuiltTree struct { + forrest *OldRebuiltForrest + + ID btrfsprim.ObjID + RootErr error Items *containers.RBTree[oldRebuiltTreeValue] Errors *containers.IntervalTree[btrfsprim.Key, oldRebuiltTreeError] @@ -135,6 +139,8 @@ func (bt *OldRebuiltForrest) RebuiltTree(ctx context.Context, treeID btrfsprim.O } 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) @@ -267,12 +273,20 @@ func (bt *OldRebuiltForrest) readNode(nodeInfo nodeInfo) *btrfstree.Node { // TreeLookup implements btrfstree.TreeOperator. func (bt *OldRebuiltForrest) TreeLookup(treeID btrfsprim.ObjID, key btrfsprim.Key) (btrfstree.Item, error) { - return bt.TreeSearch(treeID, btrfstree.SearchExactKey(key)) + return bt.RebuiltTree(bt.ctx, treeID).treeLookup(bt.ctx, key) +} + +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) { - tree := bt.RebuiltTree(bt.ctx, treeID) + 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) { if tree.RootErr != nil { return btrfstree.Item{}, tree.RootErr } @@ -284,7 +298,7 @@ func (bt *OldRebuiltForrest) TreeSearch(treeID btrfsprim.ObjID, searcher btrfstr return btrfstree.Item{}, fmt.Errorf("item with %s: %w", searcher, tree.addErrs(searcher.Search, btrfstree.ErrNoItem)) } - node := bt.readNode(indexItem.Value.Node) + node := tree.forrest.readNode(indexItem.Value.Node) defer node.Free() item := node.BodyLeaf[indexItem.Value.Slot] @@ -303,33 +317,41 @@ func (bt *OldRebuiltForrest) TreeSearchAll(treeID btrfsprim.ObjID, searcher btrf } 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 +} + +func (tree oldRebuiltTree) treeSubrange(_ 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 { node.Free() - node = bt.readNode(rbNode.Value.Node) + node = tree.forrest.readNode(rbNode.Value.Node) } - item := node.BodyLeaf[rbNode.Value.Slot] - item.Body = item.Body.CloneItem() - ret = append(ret, item) - return true + return handleFn(node.BodyLeaf[rbNode.Value.Slot]) }) node.Free() var err error - if len(ret) == 0 { + 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 ret, err + return err } func (bt *OldRebuiltForrest) TreeWalk(ctx context.Context, treeID btrfsprim.ObjID, errHandle func(*btrfstree.TreeError), cbs btrfstree.TreeWalkHandler) { @@ -344,6 +366,10 @@ func (bt *OldRebuiltForrest) TreeWalk(ctx context.Context, treeID btrfsprim.ObjI }) return } + tree.treeWalk(ctx, errHandle, cbs) +} + +func (tree oldRebuiltTree) treeWalk(ctx context.Context, errHandle func(*btrfstree.TreeError), cbs btrfstree.TreeWalkHandler) { if cbs.Item == nil { return } @@ -352,18 +378,18 @@ func (bt *OldRebuiltForrest) TreeWalk(ctx context.Context, treeID btrfsprim.ObjI if ctx.Err() != nil { return false } - if bt.ctx.Err() != nil { + if tree.forrest.ctx.Err() != nil { return false } if node == nil || node.Head.Addr != indexItem.Value.Node.LAddr { node.Free() - node = bt.readNode(indexItem.Value.Node) + node = tree.forrest.readNode(indexItem.Value.Node) } item := node.BodyLeaf[indexItem.Value.Slot] itemPath := btrfstree.Path{ { - FromTree: treeID, + FromTree: tree.ID, ToNodeAddr: indexItem.Value.Node.LAddr, ToNodeGeneration: indexItem.Value.Node.Generation, ToNodeLevel: indexItem.Value.Node.Level, -- cgit v1.1-4-g5e80 From 62a9588ff563f569469d5cf7b3b594bf109af085 Mon Sep 17 00:00:00 2001 From: Luke Shumaker Date: Thu, 2 Mar 2023 16:02:42 -0700 Subject: btrfstree: Move the implementations of methods to be on a separate tree object --- lib/btrfs/btrfstree/btree_forrest.go | 59 +++++++++++++++++++++++ lib/btrfs/btrfstree/btree_tree.go | 90 +++++++++++------------------------- lib/btrfsutil/old_rebuilt_forrest.go | 6 ++- 3 files changed, 91 insertions(+), 64 deletions(-) diff --git a/lib/btrfs/btrfstree/btree_forrest.go b/lib/btrfs/btrfstree/btree_forrest.go index acbd3f9..40adb11 100644 --- a/lib/btrfs/btrfstree/btree_forrest.go +++ b/lib/btrfs/btrfstree/btree_forrest.go @@ -78,3 +78,62 @@ func LookupTreeRoot(_ context.Context, fs TreeOperator, sb Superblock, treeID bt } } } + +type TreeOperatorImpl struct { + NodeSource +} + +func (fs TreeOperatorImpl) RawTree(ctx context.Context, treeID btrfsprim.ObjID) (*RawTree, error) { + sb, err := fs.Superblock() + if err != nil { + return nil, err + } + rootInfo, err := LookupTreeRoot(ctx, fs, *sb, treeID) + if err != nil { + return nil, err + } + return &RawTree{ + Forrest: fs, + TreeRoot: *rootInfo, + }, nil +} + +// TreeWalk implements the 'TreeOperator' interface. +func (fs TreeOperatorImpl) TreeWalk(ctx context.Context, treeID btrfsprim.ObjID, errHandle func(*TreeError), cbs TreeWalkHandler) { + tree, err := fs.RawTree(ctx, treeID) + if err != nil { + errHandle(&TreeError{Path: Path{{FromTree: treeID, ToMaxKey: btrfsprim.MaxKey}}, Err: err}) + return + } + tree.TreeWalk(ctx, errHandle, cbs) +} + +// TreeLookup implements the 'TreeOperator' interface. +func (fs TreeOperatorImpl) TreeLookup(treeID btrfsprim.ObjID, key btrfsprim.Key) (Item, error) { + ctx := context.TODO() + tree, err := fs.RawTree(ctx, treeID) + if err != nil { + return Item{}, err + } + return tree.TreeLookup(ctx, key) +} + +// TreeSearch implements the 'TreeOperator' interface. +func (fs TreeOperatorImpl) TreeSearch(treeID btrfsprim.ObjID, searcher TreeSearcher) (Item, error) { + ctx := context.TODO() + tree, err := fs.RawTree(ctx, treeID) + if err != nil { + return Item{}, err + } + return tree.TreeSearch(ctx, searcher) +} + +// TreeSearchAll implements the 'TreeOperator' interface. +func (fs TreeOperatorImpl) TreeSearchAll(treeID btrfsprim.ObjID, searcher TreeSearcher) ([]Item, error) { + ctx := context.TODO() + tree, err := fs.RawTree(ctx, treeID) + if err != nil { + return nil, err + } + return tree.TreeSearchAll(ctx, searcher) +} diff --git a/lib/btrfs/btrfstree/btree_tree.go b/lib/btrfs/btrfstree/btree_tree.go index ac7784e..e16e1c8 100644 --- a/lib/btrfs/btrfstree/btree_tree.go +++ b/lib/btrfs/btrfstree/btree_tree.go @@ -18,39 +18,24 @@ import ( "git.lukeshu.com/btrfs-progs-ng/lib/slices" ) -type TreeOperatorImpl struct { - NodeSource +type RawTree struct { + Forrest TreeOperatorImpl + TreeRoot } -// TreeWalk implements the 'TreeOperator' interface. -func (fs TreeOperatorImpl) TreeWalk(ctx context.Context, treeID btrfsprim.ObjID, errHandle func(*TreeError), cbs TreeWalkHandler) { - sb, err := fs.Superblock() - if err != nil { - errHandle(&TreeError{Path: Path{{FromTree: treeID, ToMaxKey: btrfsprim.MaxKey}}, Err: err}) - } - rootInfo, err := LookupTreeRoot(ctx, fs, *sb, treeID) - if err != nil { - errHandle(&TreeError{Path: Path{{FromTree: treeID, ToMaxKey: btrfsprim.MaxKey}}, Err: err}) - return - } - fs.RawTreeWalk(ctx, *rootInfo, errHandle, cbs) -} - -// RawTreeWalk is a utility method to help with implementing the -// 'TreeOperator' interface. -func (fs TreeOperatorImpl) RawTreeWalk(ctx context.Context, rootInfo TreeRoot, errHandle func(*TreeError), cbs TreeWalkHandler) { +func (tree *RawTree) TreeWalk(ctx context.Context, errHandle func(*TreeError), cbs TreeWalkHandler) { path := Path{{ - FromTree: rootInfo.ID, + FromTree: tree.ID, FromItemSlot: -1, - ToNodeAddr: rootInfo.RootNode, - ToNodeGeneration: rootInfo.Generation, - ToNodeLevel: rootInfo.Level, + ToNodeAddr: tree.RootNode, + ToNodeGeneration: tree.Generation, + ToNodeLevel: tree.Level, ToMaxKey: btrfsprim.MaxKey, }} - fs.treeWalk(ctx, path, errHandle, cbs) + tree.walk(ctx, path, errHandle, cbs) } -func (fs TreeOperatorImpl) treeWalk(ctx context.Context, path Path, errHandle func(*TreeError), cbs TreeWalkHandler) { +func (tree *RawTree) walk(ctx context.Context, path Path, errHandle func(*TreeError), cbs TreeWalkHandler) { if ctx.Err() != nil { return } @@ -69,7 +54,7 @@ func (fs TreeOperatorImpl) treeWalk(ctx context.Context, path Path, errHandle fu return } } - node, err := fs.ReadNode(path) + node, err := tree.Forrest.ReadNode(path) defer node.Free() if ctx.Err() != nil { return @@ -117,7 +102,7 @@ func (fs TreeOperatorImpl) treeWalk(ctx context.Context, path Path, errHandle fu return } } - fs.treeWalk(ctx, itemPath, errHandle, cbs) + tree.walk(ctx, itemPath, errHandle, cbs) if cbs.PostKeyPointer != nil { if err := cbs.PostKeyPointer(itemPath, item); err != nil { errHandle(&TreeError{Path: itemPath, Err: err}) @@ -167,20 +152,20 @@ func (fs TreeOperatorImpl) treeWalk(ctx context.Context, path Path, errHandle fu } } -func (fs TreeOperatorImpl) treeSearch(treeRoot TreeRoot, fn func(btrfsprim.Key, uint32) int) (Path, *Node, error) { +func (tree *RawTree) search(_ context.Context, fn func(btrfsprim.Key, uint32) int) (Path, *Node, error) { path := Path{{ - FromTree: treeRoot.ID, + FromTree: tree.ID, FromItemSlot: -1, - ToNodeAddr: treeRoot.RootNode, - ToNodeGeneration: treeRoot.Generation, - ToNodeLevel: treeRoot.Level, + ToNodeAddr: tree.RootNode, + ToNodeGeneration: tree.Generation, + ToNodeLevel: tree.Level, ToMaxKey: btrfsprim.MaxKey, }} for { if path.Node(-1).ToNodeAddr == 0 { return nil, nil, ErrNoItem } - node, err := fs.ReadNode(path) + node, err := tree.Forrest.ReadNode(path) if err != nil { node.Free() return nil, nil, err @@ -403,18 +388,8 @@ func (fs TreeOperatorImpl) next(path Path, node *Node) (Path, *Node, error) { return path, node, nil } -// TreeSearch implements the 'TreeOperator' interface. -func (fs TreeOperatorImpl) TreeSearch(treeID btrfsprim.ObjID, searcher TreeSearcher) (Item, error) { - ctx := context.TODO() - sb, err := fs.Superblock() - if err != nil { - return Item{}, err - } - rootInfo, err := LookupTreeRoot(ctx, fs, *sb, treeID) - if err != nil { - return Item{}, err - } - path, node, err := fs.treeSearch(*rootInfo, searcher.Search) +func (tree *RawTree) TreeSearch(ctx context.Context, searcher TreeSearcher) (Item, error) { + path, node, err := tree.search(ctx, searcher.Search) if err != nil { return Item{}, fmt.Errorf("item with %s: %w", searcher, err) } @@ -424,23 +399,12 @@ func (fs TreeOperatorImpl) TreeSearch(treeID btrfsprim.ObjID, searcher TreeSearc return item, nil } -// TreeLookup implements the 'TreeOperator' interface. -func (fs TreeOperatorImpl) TreeLookup(treeID btrfsprim.ObjID, key btrfsprim.Key) (Item, error) { - return fs.TreeSearch(treeID, SearchExactKey(key)) +func (tree *RawTree) TreeLookup(ctx context.Context, key btrfsprim.Key) (Item, error) { + return tree.TreeSearch(ctx, SearchExactKey(key)) } -// TreeSearchAll implements the 'TreeOperator' interface. -func (fs TreeOperatorImpl) TreeSearchAll(treeID btrfsprim.ObjID, searcher TreeSearcher) ([]Item, error) { - ctx := context.TODO() - sb, err := fs.Superblock() - if err != nil { - return nil, err - } - rootInfo, err := LookupTreeRoot(ctx, fs, *sb, treeID) - if err != nil { - return nil, err - } - middlePath, middleNode, err := fs.treeSearch(*rootInfo, searcher.Search) +func (tree *RawTree) TreeSearchAll(ctx context.Context, searcher TreeSearcher) ([]Item, error) { + middlePath, middleNode, err := tree.search(ctx, searcher.Search) if err != nil { return nil, fmt.Errorf("items with %s: %w", searcher, err) } @@ -450,7 +414,7 @@ func (fs TreeOperatorImpl) TreeSearchAll(treeID btrfsprim.ObjID, searcher TreeSe var errs derror.MultiError prevPath, prevNode := middlePath, middleNode for { - prevPath, prevNode, err = fs.prev(prevPath, prevNode) + prevPath, prevNode, err = tree.Forrest.prev(prevPath, prevNode) if err != nil { errs = append(errs, err) break @@ -469,7 +433,7 @@ func (fs TreeOperatorImpl) TreeSearchAll(treeID btrfsprim.ObjID, searcher TreeSe slices.Reverse(ret) if prevNode.Head.Addr != middlePath.Node(-1).ToNodeAddr { prevNode.Free() - middleNode, err = fs.ReadNode(middlePath) + middleNode, err = tree.Forrest.ReadNode(middlePath) if err != nil { middleNode.Free() return nil, fmt.Errorf("items with %s: %w", searcher, err) @@ -477,7 +441,7 @@ func (fs TreeOperatorImpl) TreeSearchAll(treeID btrfsprim.ObjID, searcher TreeSe } nextPath, nextNode := middlePath, middleNode for { - nextPath, nextNode, err = fs.next(nextPath, nextNode) + nextPath, nextNode, err = tree.Forrest.next(nextPath, nextNode) if err != nil { errs = append(errs, err) break diff --git a/lib/btrfsutil/old_rebuilt_forrest.go b/lib/btrfsutil/old_rebuilt_forrest.go index ea9ecdc..c4ba6d3 100644 --- a/lib/btrfsutil/old_rebuilt_forrest.go +++ b/lib/btrfsutil/old_rebuilt_forrest.go @@ -166,6 +166,10 @@ func (bt *OldRebuiltForrest) rawTreeWalk(ctx context.Context, treeID btrfsprim.O cacheEntry.RootErr = err return } + tree := &btrfstree.RawTree{ + Forrest: btrfstree.TreeOperatorImpl{NodeSource: bt.inner}, + TreeRoot: *root, + } errHandle := func(err *btrfstree.TreeError) { if len(err.Path) > 0 && err.Path.Node(-1).ToNodeAddr == 0 { @@ -224,7 +228,7 @@ func (bt *OldRebuiltForrest) rawTreeWalk(ctx context.Context, treeID btrfsprim.O }, } - btrfstree.TreeOperatorImpl{NodeSource: bt.inner}.RawTreeWalk(ctx, *root, errHandle, cbs) + tree.TreeWalk(ctx, errHandle, cbs) } func (tree oldRebuiltTree) addErrs(fn func(btrfsprim.Key, uint32) int, err error) error { -- cgit v1.1-4-g5e80 From d3dbadaa2eb3f14f2ad918a3ccd44a1ac224c853 Mon Sep 17 00:00:00 2001 From: Luke Shumaker Date: Mon, 20 Mar 2023 13:36:37 -0400 Subject: btrfstree: Observe io/fs.SkipDir for PreKeyPointer --- lib/btrfs/btrfstree/btree.go | 2 +- lib/btrfs/btrfstree/btree_tree.go | 3 +++ 2 files changed, 4 insertions(+), 1 deletion(-) diff --git a/lib/btrfs/btrfstree/btree.go b/lib/btrfs/btrfstree/btree.go index 9713295..0e02a06 100644 --- a/lib/btrfs/btrfstree/btree.go +++ b/lib/btrfs/btrfstree/btree.go @@ -34,7 +34,7 @@ type TreeWalkHandler struct { BadNode func(Path, *Node, error) error PostNode func(Path, *Node) error // Callbacks for items on interior nodes - PreKeyPointer func(Path, KeyPointer) error + PreKeyPointer func(Path, KeyPointer) error // io/fs.SkipDir causes the KP to not be traversed PostKeyPointer func(Path, KeyPointer) error // Callbacks for items on leaf nodes Item func(Path, Item) error diff --git a/lib/btrfs/btrfstree/btree_tree.go b/lib/btrfs/btrfstree/btree_tree.go index e16e1c8..6ef195b 100644 --- a/lib/btrfs/btrfstree/btree_tree.go +++ b/lib/btrfs/btrfstree/btree_tree.go @@ -96,6 +96,9 @@ func (tree *RawTree) walk(ctx context.Context, path Path, errHandle func(*TreeEr }) if cbs.PreKeyPointer != nil { if err := cbs.PreKeyPointer(itemPath, item); err != nil { + if errors.Is(err, iofs.SkipDir) { + continue + } errHandle(&TreeError{Path: itemPath, Err: err}) } if ctx.Err() != nil { -- cgit v1.1-4-g5e80 From 6ebccb12a4234e6202afb4aa362aa97d125e089e Mon Sep 17 00:00:00 2001 From: Luke Shumaker Date: Mon, 20 Mar 2023 18:00:26 -0400 Subject: btrfstree: Rework the RawTree implementation to be built around TreeWalk --- lib/btrfs/btrfstree/btree_forrest.go | 10 +- lib/btrfs/btrfstree/btree_tree.go | 414 +++++++++++------------------------ 2 files changed, 131 insertions(+), 293 deletions(-) diff --git a/lib/btrfs/btrfstree/btree_forrest.go b/lib/btrfs/btrfstree/btree_forrest.go index 40adb11..f7182d8 100644 --- a/lib/btrfs/btrfstree/btree_forrest.go +++ b/lib/btrfs/btrfstree/btree_forrest.go @@ -135,5 +135,13 @@ func (fs TreeOperatorImpl) TreeSearchAll(treeID btrfsprim.ObjID, searcher TreeSe if err != nil { return nil, err } - return tree.TreeSearchAll(ctx, searcher) + + 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/btrfstree/btree_tree.go b/lib/btrfs/btrfstree/btree_tree.go index 6ef195b..35c166f 100644 --- a/lib/btrfs/btrfstree/btree_tree.go +++ b/lib/btrfs/btrfstree/btree_tree.go @@ -155,314 +155,144 @@ func (tree *RawTree) walk(ctx context.Context, path Path, errHandle func(*TreeEr } } -func (tree *RawTree) search(_ context.Context, fn func(btrfsprim.Key, uint32) int) (Path, *Node, error) { - path := Path{{ - FromTree: tree.ID, - FromItemSlot: -1, - ToNodeAddr: tree.RootNode, - ToNodeGeneration: tree.Generation, - ToNodeLevel: tree.Level, - ToMaxKey: btrfsprim.MaxKey, - }} - for { - if path.Node(-1).ToNodeAddr == 0 { - return nil, nil, ErrNoItem - } - node, err := tree.Forrest.ReadNode(path) - if err != nil { - node.Free() - return nil, nil, err - } - - switch { - case node.Head.Level > 0: - // interior node - - // Search for the right-most node.BodyInterior item for which - // `fn(item.Key) >= 0`. - // - // + + + + 0 - - - - - // - // There may or may not be a value that returns '0'. - // - // i.e. find the highest value that isn't too high. - lastGood, ok := slices.SearchHighest(node.BodyInterior, func(kp KeyPointer) int { - return slices.Min(fn(kp.Key, math.MaxUint32), 0) // don't return >0; a key can't be "too low" - }) - if !ok { - node.Free() - return nil, nil, ErrNoItem - } - toMaxKey := path.Node(-1).ToMaxKey - if lastGood+1 < len(node.BodyInterior) { - toMaxKey = node.BodyInterior[lastGood+1].Key.Mm() - } - path = append(path, PathElem{ - FromTree: node.Head.Owner, - FromItemSlot: lastGood, - ToNodeAddr: node.BodyInterior[lastGood].BlockPtr, - ToNodeGeneration: node.BodyInterior[lastGood].Generation, - ToNodeLevel: node.Head.Level - 1, - ToKey: node.BodyInterior[lastGood].Key, - ToMaxKey: toMaxKey, - }) - node.Free() - default: - // leaf node - - // Search for a member of node.BodyLeaf for which - // `fn(item.Head.Key) == 0`. - // - // + + + + 0 - - - - - // - // Such an item might not exist; in this case, return (nil, ErrNoItem). - // Multiple such items might exist; in this case, it does not matter which - // is returned. - // - // Implement this search as a binary search. - slot, ok := slices.Search(node.BodyLeaf, func(item Item) int { - return fn(item.Key, item.BodySize) - }) - if !ok { - node.Free() - return nil, nil, ErrNoItem - } - path = append(path, PathElem{ - FromTree: node.Head.Owner, - FromItemSlot: slot, - ToKey: node.BodyLeaf[slot].Key, - ToMaxKey: node.BodyLeaf[slot].Key, - }) - return path, node, nil - } - } -} - -func (fs TreeOperatorImpl) prev(path Path, node *Node) (Path, *Node, error) { - var err error - path = path.DeepCopy() - - // go up - for path.Node(-1).FromItemSlot < 1 { - path = path.Parent() - if len(path) == 0 { - return nil, nil, nil - } - } - // go left - path.Node(-1).FromItemSlot-- - if path.Node(-1).ToNodeAddr != 0 { - if node.Head.Addr != path.Node(-2).ToNodeAddr { - node.Free() - node, err = fs.ReadNode(path.Parent()) - if err != nil { - node.Free() - return nil, nil, err - } - path.Node(-1).ToNodeAddr = node.BodyInterior[path.Node(-1).FromItemSlot].BlockPtr - } - } - // go down - for path.Node(-1).ToNodeAddr != 0 { - if node.Head.Addr != path.Node(-1).ToNodeAddr { - node.Free() - node, err = fs.ReadNode(path) - if err != nil { - node.Free() - return nil, nil, err - } - } - if node.Head.Level > 0 { - path = append(path, PathElem{ - FromTree: node.Head.Owner, - FromItemSlot: len(node.BodyInterior) - 1, - ToNodeAddr: node.BodyInterior[len(node.BodyInterior)-1].BlockPtr, - ToNodeGeneration: node.BodyInterior[len(node.BodyInterior)-1].Generation, - ToNodeLevel: node.Head.Level - 1, - ToKey: node.BodyInterior[len(node.BodyInterior)-1].Key, - ToMaxKey: path.Node(-1).ToMaxKey, - }) - } else { - path = append(path, PathElem{ - FromTree: node.Head.Owner, - FromItemSlot: len(node.BodyLeaf) - 1, - ToKey: node.BodyLeaf[len(node.BodyLeaf)-1].Key, - ToMaxKey: node.BodyLeaf[len(node.BodyLeaf)-1].Key, - }) - } +// searchKP takes a sorted list of KeyPointers, and finds the +// +// - left-most member for which `searchFn(member.Key, math.MaxUint32) == 0`; or else the +// - right-most member for which `searchFn(member.Key, math.MaxUint32) == 1`; or else +// - zero +// +// This assumes that `haystack` is sorted such that the return values from searchFn look like: +// +// - + + 0 0 0 - - - +func searchKP(haystack []KeyPointer, searchFn func(key btrfsprim.Key, size uint32) int) (_ KeyPointer, ok bool) { + if leftZero, ok := slices.SearchLowest(haystack, func(kp KeyPointer) int { + return searchFn(kp.Key, math.MaxUint32) + }); ok { + return haystack[leftZero], true } - // return - if node.Head.Addr != path.Node(-2).ToNodeAddr { - node.Free() - node, err = fs.ReadNode(path.Parent()) - if err != nil { - node.Free() - return nil, nil, err - } + if rightPos, ok := slices.SearchHighest(haystack, func(kp KeyPointer) int { + return slices.Min(searchFn(kp.Key, math.MaxUint32), 0) + }); ok { + return haystack[rightPos], true } - return path, node, nil + return KeyPointer{}, false } -func (fs TreeOperatorImpl) next(path Path, node *Node) (Path, *Node, error) { - var err error - path = path.DeepCopy() +func (tree *RawTree) TreeSearch(ctx context.Context, searcher TreeSearcher) (Item, error) { + ctx, cancel := context.WithCancel(ctx) + var retErr error - // go up - if node.Head.Addr != path.Node(-2).ToNodeAddr { - node.Free() - node, err = fs.ReadNode(path.Parent()) - if err != nil { - node.Free() - return nil, nil, err + var ret Item + var selKP KeyPointer + tree.TreeWalk(ctx, func(err *TreeError) { + if retErr == nil { + retErr = fmt.Errorf("item with %s: %w", searcher, err) } - path.Node(-2).ToNodeLevel = node.Head.Level - } - for path.Node(-1).FromItemSlot+1 >= int(node.Head.NumItems) { - path = path.Parent() - if len(path) == 1 { - return nil, nil, nil - } - if node.Head.Addr != path.Node(-2).ToNodeAddr { - node.Free() - node, err = fs.ReadNode(path.Parent()) - if err != nil { - node.Free() - return nil, nil, err - } - path.Node(-2).ToNodeLevel = node.Head.Level - } - } - // go right - path.Node(-1).FromItemSlot++ - if path.Node(-1).ToNodeAddr != 0 { - if node.Head.Addr != path.Node(-2).ToNodeAddr { - node.Free() - node, err = fs.ReadNode(path.Parent()) - if err != nil { - node.Free() - return nil, nil, err - } - path.Node(-1).ToNodeAddr = node.BodyInterior[path.Node(-1).FromItemSlot].BlockPtr - } - } - // go down - for path.Node(-1).ToNodeAddr != 0 { - if node.Head.Addr != path.Node(-1).ToNodeAddr { - node.Free() - node, err = fs.ReadNode(path) - if err != nil { - node.Free() - return nil, nil, err + cancel() + }, TreeWalkHandler{ + Node: func(_ Path, node *Node) error { + if node.Head.Level > 0 { // interior node + kp, ok := searchKP(node.BodyInterior, searcher.Search) + if !ok { + return ErrNoItem + } + selKP = kp + } else { // leaf node + slot, ok := slices.Search(node.BodyLeaf, func(item Item) int { + return searcher.Search(item.Key, item.BodySize) + }) + if !ok { + return ErrNoItem + } + ret = node.BodyLeaf[slot] + ret.Body = ret.Body.CloneItem() } - path.Node(-1).ToNodeLevel = node.Head.Level - } - if node.Head.Level > 0 { - toMaxKey := path.Node(-1).ToMaxKey - if len(node.BodyInterior) > 1 { - toMaxKey = node.BodyInterior[1].Key.Mm() + return nil + }, + PreKeyPointer: func(_ Path, kp KeyPointer) error { + if kp == selKP { + return nil } - path = append(path, PathElem{ - FromTree: node.Head.Owner, - FromItemSlot: 0, - ToNodeAddr: node.BodyInterior[0].BlockPtr, - ToNodeGeneration: node.BodyInterior[0].Generation, - ToNodeLevel: node.Head.Level - 1, - ToKey: node.BodyInterior[0].Key, - ToMaxKey: toMaxKey, - }) - } else { - path = append(path, PathElem{ - FromTree: node.Head.Owner, - FromItemSlot: 0, - ToKey: node.BodyInterior[0].Key, - ToMaxKey: node.BodyInterior[0].Key, - }) - } - } - // return - if node.Head.Addr != path.Node(-2).ToNodeAddr { - node.Free() - node, err = fs.ReadNode(path.Parent()) - if err != nil { - node.Free() - return nil, nil, err - } - } - return path, node, nil -} + return iofs.SkipDir + }, + }) -func (tree *RawTree) TreeSearch(ctx context.Context, searcher TreeSearcher) (Item, error) { - path, node, err := tree.search(ctx, searcher.Search) - if err != nil { - return Item{}, fmt.Errorf("item with %s: %w", searcher, err) - } - item := node.BodyLeaf[path.Node(-1).FromItemSlot] - item.Body = item.Body.CloneItem() - node.Free() - return item, nil + return ret, retErr } func (tree *RawTree) TreeLookup(ctx context.Context, key btrfsprim.Key) (Item, error) { return tree.TreeSearch(ctx, SearchExactKey(key)) } -func (tree *RawTree) TreeSearchAll(ctx context.Context, searcher TreeSearcher) ([]Item, error) { - middlePath, middleNode, err := tree.search(ctx, searcher.Search) - if err != nil { - return nil, fmt.Errorf("items with %s: %w", searcher, err) - } - middleItem := middleNode.BodyLeaf[middlePath.Node(-1).FromItemSlot] - - ret := []Item{middleItem} +func (tree *RawTree) TreeSubrange(ctx context.Context, min int, searcher TreeSearcher, handleFn func(Item) bool) error { + ctx, cancel := context.WithCancel(ctx) var errs derror.MultiError - prevPath, prevNode := middlePath, middleNode - for { - prevPath, prevNode, err = tree.Forrest.prev(prevPath, prevNode) - if err != nil { - errs = append(errs, err) - break - } - if len(prevPath) == 0 { - break - } - prevItem := prevNode.BodyLeaf[prevPath.Node(-1).FromItemSlot] - if searcher.Search(prevItem.Key, prevItem.BodySize) != 0 { - break - } - item := prevItem - item.Body = item.Body.CloneItem() - ret = append(ret, item) - } - slices.Reverse(ret) - if prevNode.Head.Addr != middlePath.Node(-1).ToNodeAddr { - prevNode.Free() - middleNode, err = tree.Forrest.ReadNode(middlePath) - if err != nil { - middleNode.Free() - return nil, fmt.Errorf("items with %s: %w", searcher, err) - } - } - nextPath, nextNode := middlePath, middleNode - for { - nextPath, nextNode, err = tree.Forrest.next(nextPath, nextNode) - if err != nil { - errs = append(errs, err) - break - } - if len(nextPath) == 0 { - break - } - nextItem := nextNode.BodyLeaf[nextPath.Node(-1).FromItemSlot] - if searcher.Search(nextItem.Key, nextItem.BodySize) != 0 { - break - } - item := nextItem - item.Body = item.Body.CloneItem() - ret = append(ret, item) + + var minKP btrfsprim.Key + var cnt int + tree.TreeWalk(ctx, func(err *TreeError) { + errs = append(errs, err) + }, TreeWalkHandler{ + Node: func(_ Path, node *Node) error { + // Only bother for interior nodes. + if node.Head.Level == 0 { + return nil + } + kp, ok := searchKP(node.BodyInterior, searcher.Search) + if !ok { + cancel() + return nil + } + minKP = kp.Key + return nil + }, + PreKeyPointer: func(_ Path, kp KeyPointer) error { + if searcher.Search(kp.Key, math.MaxUint32) < 0 { + cancel() + return iofs.SkipDir + } + if kp.Key.Compare(minKP) > 0 { + return iofs.SkipDir + } + return nil + }, + Item: func(_ Path, item Item) error { + d := searcher.Search(item.Key, item.BodySize) + switch { + case d > 1: + // do nothing + case d == 0: + cnt++ + if !handleFn(item) { + cancel() + } + case d < 1: + cancel() + } + return nil + }, + BadItem: func(_ Path, item Item) error { + d := searcher.Search(item.Key, item.BodySize) + switch { + case d > 1: + // do nothing + case d == 0: + cnt++ + if !handleFn(item) { + cancel() + } + case d < 1: + cancel() + } + return nil + }, + }) + + if cnt < min { + errs = append(errs, ErrNoItem) } - nextNode.Free() - if errs != nil { - err = errs + if len(errs) > 0 { + return fmt.Errorf("items with %s: %w", searcher, errs) } - return ret, err + return nil } -- cgit v1.1-4-g5e80 From b8185f8e741bd81e0d6f6416e46e11f6f7570995 Mon Sep 17 00:00:00 2001 From: Luke Shumaker Date: Thu, 2 Mar 2023 16:02:42 -0700 Subject: btrfstree: Fuss with the TreeWalk API --- cmd/btrfs-rec/inspect/dumptrees/print_tree.go | 15 +- cmd/btrfs-rec/inspect_lstrees.go | 14 +- cmd/btrfs-rec/inspect_spewitems.go | 6 +- lib/btrfs/btrfstree/btree.go | 60 +++---- lib/btrfs/btrfstree/btree_forrest.go | 2 +- lib/btrfs/btrfstree/btree_tree.go | 221 +++++++++++--------------- lib/btrfs/io2_lv.go | 7 +- lib/btrfs/io3_btree.go | 5 +- lib/btrfsutil/old_rebuilt_forrest.go | 63 ++++---- lib/btrfsutil/walk.go | 5 +- 10 files changed, 178 insertions(+), 220 deletions(-) diff --git a/cmd/btrfs-rec/inspect/dumptrees/print_tree.go b/cmd/btrfs-rec/inspect/dumptrees/print_tree.go index 60303e9..7703078 100644 --- a/cmd/btrfs-rec/inspect/dumptrees/print_tree.go +++ b/cmd/btrfs-rec/inspect/dumptrees/print_tree.go @@ -53,9 +53,9 @@ func DumpTrees(ctx context.Context, out io.Writer, fs *btrfs.FS) { dlog.Error(ctx, err) }, btrfstree.TreeWalkHandler{ - Item: func(_ btrfstree.Path, item btrfstree.Item) error { + Item: func(_ btrfstree.Path, item btrfstree.Item) { if item.Key.ItemType != btrfsitem.ROOT_ITEM_KEY { - return nil + return } treeName, ok := map[btrfsprim.ObjID]string{ btrfsprim.ROOT_TREE_OBJECTID: "root", @@ -82,7 +82,6 @@ func DumpTrees(ctx context.Context, out io.Writer, fs *btrfs.FS) { } 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 }, }, ) @@ -99,20 +98,19 @@ var nodeHeaderSize = binstruct.StaticSize(btrfstree.NodeHeader{}) func printTree(ctx context.Context, out io.Writer, fs *btrfs.FS, treeID btrfsprim.ObjID) { var itemOffset uint32 handlers := btrfstree.TreeWalkHandler{ - Node: func(path btrfstree.Path, node *btrfstree.Node) error { + Node: func(path btrfstree.Path, node *btrfstree.Node) { printHeaderInfo(out, node) itemOffset = node.Size - uint32(nodeHeaderSize) - return nil }, - PreKeyPointer: func(path btrfstree.Path, item btrfstree.KeyPointer) error { + KeyPointer: func(path btrfstree.Path, item btrfstree.KeyPointer) bool { treeID := path[0].FromTree textui.Fprintf(out, "\tkey %v block %v gen %v\n", item.Key.Format(treeID), item.BlockPtr, item.Generation) - return nil + return true }, - Item: func(path btrfstree.Path, item btrfstree.Item) error { + Item: func(path btrfstree.Path, item btrfstree.Item) { treeID := path[0].FromTree i := path.Node(-1).FromItemSlot bs, _ := binstruct.Marshal(item.Body) @@ -359,7 +357,6 @@ func printTree(ctx context.Context, out io.Writer, fs *btrfs.FS, treeID btrfspri default: textui.Fprintf(out, "\t\t(error) unhandled item type: %T\n", body) } - return nil }, } handlers.BadItem = handlers.Item diff --git a/cmd/btrfs-rec/inspect_lstrees.go b/cmd/btrfs-rec/inspect_lstrees.go index cad1a37..1449a21 100644 --- a/cmd/btrfs-rec/inspect_lstrees.go +++ b/cmd/btrfs-rec/inspect_lstrees.go @@ -75,19 +75,21 @@ func init() { treeErrCnt++ }, TreeWalkHandler: btrfstree.TreeWalkHandler{ - Node: func(path btrfstree.Path, node *btrfstree.Node) error { + Node: func(path btrfstree.Path, node *btrfstree.Node) { visitedNodes.Insert(path.Node(-1).ToNodeAddr) - return nil }, - Item: func(_ btrfstree.Path, item btrfstree.Item) error { + BadNode: func(path btrfstree.Path, node *btrfstree.Node, err error) bool { + visitedNodes.Insert(path.Node(-1).ToNodeAddr) + treeErrCnt++ + return false + }, + Item: func(_ btrfstree.Path, item btrfstree.Item) { typ := item.Key.ItemType treeItemCnt[typ]++ - return nil }, - BadItem: func(_ btrfstree.Path, item btrfstree.Item) error { + BadItem: func(_ btrfstree.Path, item btrfstree.Item) { typ := item.Key.ItemType treeItemCnt[typ]++ - return nil }, }, PostTree: func(_ string, _ btrfsprim.ObjID) { diff --git a/cmd/btrfs-rec/inspect_spewitems.go b/cmd/btrfs-rec/inspect_spewitems.go index b83e989..c3a1e6b 100644 --- a/cmd/btrfs-rec/inspect_spewitems.go +++ b/cmd/btrfs-rec/inspect_spewitems.go @@ -34,17 +34,15 @@ func init() { dlog.Error(ctx, err) }, TreeWalkHandler: btrfstree.TreeWalkHandler{ - Item: func(path btrfstree.Path, item btrfstree.Item) error { + Item: func(path btrfstree.Path, item btrfstree.Item) { textui.Fprintf(os.Stdout, "%s = ", path) spew.Dump(item) _, _ = os.Stdout.WriteString("\n") - return nil }, - BadItem: func(path btrfstree.Path, item btrfstree.Item) error { + BadItem: func(path btrfstree.Path, item btrfstree.Item) { textui.Fprintf(os.Stdout, "%s = ", path) spew.Dump(item) _, _ = os.Stdout.WriteString("\n") - return nil }, }, }) diff --git a/lib/btrfs/btrfstree/btree.go b/lib/btrfs/btrfstree/btree.go index 0e02a06..bc1bac2 100644 --- a/lib/btrfs/btrfstree/btree.go +++ b/lib/btrfs/btrfstree/btree.go @@ -23,22 +23,24 @@ type TreeSearcher interface { } type TreeWalkHandler struct { + BadSuperblock func(error) + // Callbacks for entire nodes. // - // If any of these return an error that is io/fs.SkipDir, the - // node immediately stops getting processed; if PreNode, Node, - // or BadNode return io/fs.SkipDir then key pointers and items - // within the node are not processed. - PreNode func(Path) error - Node func(Path, *Node) error - BadNode func(Path, *Node, error) error - PostNode func(Path, *Node) error - // Callbacks for items on interior nodes - PreKeyPointer func(Path, KeyPointer) error // io/fs.SkipDir causes the KP to not be traversed - PostKeyPointer func(Path, KeyPointer) error - // Callbacks for items on leaf nodes - Item func(Path, Item) error - BadItem func(Path, Item) error + // The return value from BadNode is whether to process the + // slots in this node or not; if no BadNode function is given, + // then it is not processed. + Node func(Path, *Node) + BadNode func(Path, *Node, error) bool + + // Callbacks for slots in nodes. + // + // The return value from KeyPointer is whether to recurse or + // not; if no KeyPointer function is given, then it is + // recursed. + KeyPointer func(Path, KeyPointer) bool + Item func(Path, Item) + BadItem func(Path, Item) } // TreeOperator is an interface for performing basic btree operations. @@ -46,25 +48,25 @@ 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. + // 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. + // Canceling the Context causes TreeWalk to return early; no values + // from the Context are used. // // The lifecycle of callbacks is: // - // 001 .PreNode() - // 002 (read node) - // 003 .Node() (or .BadNode()) - // for item in node.items: - // if interior: - // 004 .PreKeyPointer() - // 005 (recurse) - // 006 .PostKeyPointer() - // else: - // 004 .Item() (or .BadItem()) - // 007 .PostNode() + // 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) diff --git a/lib/btrfs/btrfstree/btree_forrest.go b/lib/btrfs/btrfstree/btree_forrest.go index f7182d8..8f8e2de 100644 --- a/lib/btrfs/btrfstree/btree_forrest.go +++ b/lib/btrfs/btrfstree/btree_forrest.go @@ -105,7 +105,7 @@ func (fs TreeOperatorImpl) TreeWalk(ctx context.Context, treeID btrfsprim.ObjID, errHandle(&TreeError{Path: Path{{FromTree: treeID, ToMaxKey: btrfsprim.MaxKey}}, Err: err}) return } - tree.TreeWalk(ctx, errHandle, cbs) + tree.TreeWalk(ctx, cbs) } // TreeLookup implements the 'TreeOperator' interface. diff --git a/lib/btrfs/btrfstree/btree_tree.go b/lib/btrfs/btrfstree/btree_tree.go index 35c166f..a943803 100644 --- a/lib/btrfs/btrfstree/btree_tree.go +++ b/lib/btrfs/btrfstree/btree_tree.go @@ -6,9 +6,7 @@ package btrfstree import ( "context" - "errors" "fmt" - iofs "io/fs" "math" "github.com/datawire/dlib/derror" @@ -23,7 +21,7 @@ type RawTree struct { TreeRoot } -func (tree *RawTree) TreeWalk(ctx context.Context, errHandle func(*TreeError), cbs TreeWalkHandler) { +func (tree *RawTree) TreeWalk(ctx context.Context, cbs TreeWalkHandler) { path := Path{{ FromTree: tree.ID, FromItemSlot: -1, @@ -32,10 +30,10 @@ func (tree *RawTree) TreeWalk(ctx context.Context, errHandle func(*TreeError), c ToNodeLevel: tree.Level, ToMaxKey: btrfsprim.MaxKey, }} - tree.walk(ctx, path, errHandle, cbs) + tree.walk(ctx, path, cbs) } -func (tree *RawTree) walk(ctx context.Context, path Path, errHandle func(*TreeError), cbs TreeWalkHandler) { +func (tree *RawTree) walk(ctx context.Context, path Path, cbs TreeWalkHandler) { if ctx.Err() != nil { return } @@ -43,114 +41,85 @@ func (tree *RawTree) walk(ctx context.Context, path Path, errHandle func(*TreeEr return } - if cbs.PreNode != nil { - if err := cbs.PreNode(path); err != nil { - if errors.Is(err, iofs.SkipDir) { - return - } - errHandle(&TreeError{Path: path, Err: err}) + // 001 + node, err := tree.Forrest.ReadNode(path) + defer node.Free() + if ctx.Err() != nil { + return + } + + // 002 + switch { + case err == nil: + if cbs.Node != nil { + cbs.Node(path, node) } - if ctx.Err() != nil { + default: + process := cbs.BadNode != nil && cbs.BadNode(path, node, err) + if !process { return } } - node, err := tree.Forrest.ReadNode(path) - defer node.Free() if ctx.Err() != nil { return } - if err != nil && node != nil && cbs.BadNode != nil { - // opportunity to fix the node - err = cbs.BadNode(path, node, err) - if errors.Is(err, iofs.SkipDir) { + + // 003-004 + if node == nil { + return + } + // branch a (interior) + for i, item := range node.BodyInterior { + toMaxKey := path.Node(-1).ToMaxKey + if i+1 < len(node.BodyInterior) { + toMaxKey = node.BodyInterior[i+1].Key.Mm() + } + itemPath := append(path, PathElem{ + FromTree: node.Head.Owner, + FromItemSlot: i, + ToNodeAddr: item.BlockPtr, + ToNodeGeneration: item.Generation, + ToNodeLevel: node.Head.Level - 1, + ToKey: item.Key, + ToMaxKey: toMaxKey, + }) + // 003a + recurse := cbs.KeyPointer == nil || cbs.KeyPointer(itemPath, item) + if ctx.Err() != nil { return } - } - if err != nil { - errHandle(&TreeError{Path: path, Err: err}) - } else if cbs.Node != nil { - if err := cbs.Node(path, node); err != nil { - if errors.Is(err, iofs.SkipDir) { + // 004a + if recurse { + tree.walk(ctx, itemPath, cbs) + if ctx.Err() != nil { return } - errHandle(&TreeError{Path: path, Err: err}) } } - if ctx.Err() != nil { + // branch b (leaf) + if cbs.Item == nil && cbs.BadItem == nil { return } - if node != nil { - for i, item := range node.BodyInterior { - toMaxKey := path.Node(-1).ToMaxKey - if i+1 < len(node.BodyInterior) { - toMaxKey = node.BodyInterior[i+1].Key.Mm() - } - itemPath := append(path, PathElem{ - FromTree: node.Head.Owner, - FromItemSlot: i, - ToNodeAddr: item.BlockPtr, - ToNodeGeneration: item.Generation, - ToNodeLevel: node.Head.Level - 1, - ToKey: item.Key, - ToMaxKey: toMaxKey, - }) - if cbs.PreKeyPointer != nil { - if err := cbs.PreKeyPointer(itemPath, item); err != nil { - if errors.Is(err, iofs.SkipDir) { - continue - } - errHandle(&TreeError{Path: itemPath, Err: err}) - } - if ctx.Err() != nil { - return - } - } - tree.walk(ctx, itemPath, errHandle, cbs) - if cbs.PostKeyPointer != nil { - if err := cbs.PostKeyPointer(itemPath, item); err != nil { - errHandle(&TreeError{Path: itemPath, Err: err}) - } - if ctx.Err() != nil { - return - } + for i, item := range node.BodyLeaf { + itemPath := append(path, PathElem{ + FromTree: node.Head.Owner, + FromItemSlot: i, + ToKey: item.Key, + ToMaxKey: item.Key, + }) + // 003b + switch item.Body.(type) { + case *btrfsitem.Error: + if cbs.BadItem != nil { + cbs.BadItem(itemPath, item) } - } - for i, item := range node.BodyLeaf { - itemPath := append(path, PathElem{ - FromTree: node.Head.Owner, - FromItemSlot: i, - ToKey: item.Key, - ToMaxKey: item.Key, - }) - if errBody, isErr := item.Body.(*btrfsitem.Error); isErr { - if cbs.BadItem == nil { - errHandle(&TreeError{Path: itemPath, Err: errBody.Err}) - } else { - if err := cbs.BadItem(itemPath, item); err != nil { - errHandle(&TreeError{Path: itemPath, Err: err}) - } - if ctx.Err() != nil { - return - } - } - } else { - if cbs.Item != nil { - if err := cbs.Item(itemPath, item); err != nil { - errHandle(&TreeError{Path: itemPath, Err: err}) - } - if ctx.Err() != nil { - return - } - } + default: + if cbs.Item != nil { + cbs.Item(itemPath, item) } } - } - if cbs.PostNode != nil { - if err := cbs.PostNode(path, node); err != nil { - if errors.Is(err, iofs.SkipDir) { - return - } - errHandle(&TreeError{Path: path, Err: err}) + if ctx.Err() != nil { + return } } } @@ -181,20 +150,22 @@ func searchKP(haystack []KeyPointer, searchFn func(key btrfsprim.Key, size uint3 func (tree *RawTree) TreeSearch(ctx context.Context, searcher TreeSearcher) (Item, error) { ctx, cancel := context.WithCancel(ctx) var retErr error - - var ret Item - var selKP KeyPointer - tree.TreeWalk(ctx, func(err *TreeError) { - if retErr == nil { + setErr := func(err error) { + if retErr == nil && err != nil { retErr = fmt.Errorf("item with %s: %w", searcher, err) } cancel() - }, TreeWalkHandler{ - Node: func(_ Path, node *Node) error { + } + + var ret Item + var selKP KeyPointer + tree.TreeWalk(ctx, TreeWalkHandler{ + Node: func(_ Path, node *Node) { if node.Head.Level > 0 { // interior node kp, ok := searchKP(node.BodyInterior, searcher.Search) if !ok { - return ErrNoItem + setErr(ErrNoItem) + return } selKP = kp } else { // leaf node @@ -202,18 +173,19 @@ func (tree *RawTree) TreeSearch(ctx context.Context, searcher TreeSearcher) (Ite return searcher.Search(item.Key, item.BodySize) }) if !ok { - return ErrNoItem + setErr(ErrNoItem) + return } ret = node.BodyLeaf[slot] ret.Body = ret.Body.CloneItem() } - return nil }, - PreKeyPointer: func(_ Path, kp KeyPointer) error { - if kp == selKP { - return nil - } - return iofs.SkipDir + BadNode: func(path Path, _ *Node, err error) bool { + setErr(fmt.Errorf("%v: %w", path, err)) + return false + }, + KeyPointer: func(_ Path, kp KeyPointer) bool { + return kp == selKP }, }) @@ -230,33 +202,34 @@ func (tree *RawTree) TreeSubrange(ctx context.Context, min int, searcher TreeSea var minKP btrfsprim.Key var cnt int - tree.TreeWalk(ctx, func(err *TreeError) { - errs = append(errs, err) - }, TreeWalkHandler{ - Node: func(_ Path, node *Node) error { + tree.TreeWalk(ctx, TreeWalkHandler{ + Node: func(_ Path, node *Node) { // Only bother for interior nodes. if node.Head.Level == 0 { - return nil + return } kp, ok := searchKP(node.BodyInterior, searcher.Search) if !ok { cancel() - return nil + return } minKP = kp.Key - return nil }, - PreKeyPointer: func(_ Path, kp KeyPointer) error { + BadNode: func(path Path, _ *Node, err error) bool { + errs = append(errs, fmt.Errorf("%v: %w", path, err)) + return false + }, + KeyPointer: func(_ Path, kp KeyPointer) bool { if searcher.Search(kp.Key, math.MaxUint32) < 0 { cancel() - return iofs.SkipDir + return false } if kp.Key.Compare(minKP) > 0 { - return iofs.SkipDir + return false } - return nil + return true }, - Item: func(_ Path, item Item) error { + Item: func(_ Path, item Item) { d := searcher.Search(item.Key, item.BodySize) switch { case d > 1: @@ -269,9 +242,8 @@ func (tree *RawTree) TreeSubrange(ctx context.Context, min int, searcher TreeSea case d < 1: cancel() } - return nil }, - BadItem: func(_ Path, item Item) error { + BadItem: func(_ Path, item Item) { d := searcher.Search(item.Key, item.BodySize) switch { case d > 1: @@ -284,7 +256,6 @@ func (tree *RawTree) TreeSubrange(ctx context.Context, min int, searcher TreeSea case d < 1: cancel() } - return nil }, }) diff --git a/lib/btrfs/io2_lv.go b/lib/btrfs/io2_lv.go index d05d51f..9f4e53f 100644 --- a/lib/btrfs/io2_lv.go +++ b/lib/btrfs/io2_lv.go @@ -168,15 +168,15 @@ func (fs *FS) initDev(ctx context.Context, sb btrfstree.Superblock) error { errs = append(errs, err) }, btrfstree.TreeWalkHandler{ - Item: func(_ btrfstree.Path, item btrfstree.Item) error { + Item: func(_ btrfstree.Path, item btrfstree.Item) { if item.Key.ItemType != btrfsitem.CHUNK_ITEM_KEY { - return nil + return } switch itemBody := item.Body.(type) { case *btrfsitem.Chunk: for _, mapping := range itemBody.Mappings(item.Key) { if err := fs.LV.AddMapping(mapping); err != nil { - return err + errs = append(errs, err) } } case *btrfsitem.Error: @@ -187,7 +187,6 @@ func (fs *FS) initDev(ctx context.Context, sb btrfstree.Superblock) error { // updated. panic(fmt.Errorf("should not happen: CHUNK_ITEM has unexpected item type: %T", itemBody)) } - return nil }, }, ) diff --git a/lib/btrfs/io3_btree.go b/lib/btrfs/io3_btree.go index 80ab10f..6df88f5 100644 --- a/lib/btrfs/io3_btree.go +++ b/lib/btrfs/io3_btree.go @@ -37,15 +37,14 @@ func (fs *FS) populateTreeUUIDs(ctx context.Context) { // do nothing }, btrfstree.TreeWalkHandler{ - Item: func(_ btrfstree.Path, item btrfstree.Item) error { + Item: func(_ btrfstree.Path, item btrfstree.Item) { itemBody, ok := item.Body.(*btrfsitem.Root) if !ok { - return nil + return } fs.cacheObjID2UUID[item.Key.ObjectID] = itemBody.UUID fs.cacheTreeParent[item.Key.ObjectID] = itemBody.ParentUUID fs.cacheUUID2ObjID[itemBody.UUID] = item.Key.ObjectID - return nil }, }, ) diff --git a/lib/btrfsutil/old_rebuilt_forrest.go b/lib/btrfsutil/old_rebuilt_forrest.go index c4ba6d3..bb5ab59 100644 --- a/lib/btrfsutil/old_rebuilt_forrest.go +++ b/lib/btrfsutil/old_rebuilt_forrest.go @@ -13,6 +13,7 @@ import ( "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" @@ -171,35 +172,17 @@ func (bt *OldRebuiltForrest) rawTreeWalk(ctx context.Context, treeID btrfsprim.O TreeRoot: *root, } - errHandle := 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(oldRebuiltTreeError{ - Min: err.Path.Node(-1).ToKey, - Max: err.Path.Node(-1).ToMaxKey, - Err: err.Err, - }) - } - var curNode nodeInfo cbs := btrfstree.TreeWalkHandler{ - BadNode: func(path btrfstree.Path, node *btrfstree.Node, err error) error { - if node != nil { - curNode = nodeInfo{ - LAddr: path.Node(-1).ToNodeAddr, - Level: node.Head.Level, - Generation: node.Head.Generation, - Owner: node.Head.Owner, - MinItem: discardOK(node.MinItem()), - MaxItem: discardOK(node.MaxItem()), - } - } - return err + BadNode: func(path btrfstree.Path, node *btrfstree.Node, err error) bool { + cacheEntry.Errors.Insert(oldRebuiltTreeError{ + Min: path.Node(-1).ToKey, + Max: path.Node(-1).ToMaxKey, + Err: err, + }) + return false }, - Node: func(path btrfstree.Path, node *btrfstree.Node) error { + Node: func(path btrfstree.Path, node *btrfstree.Node) { curNode = nodeInfo{ LAddr: path.Node(-1).ToNodeAddr, Level: node.Head.Level, @@ -208,9 +191,8 @@ func (bt *OldRebuiltForrest) rawTreeWalk(ctx context.Context, treeID btrfsprim.O MinItem: discardOK(node.MinItem()), MaxItem: discardOK(node.MaxItem()), } - return nil }, - Item: func(path btrfstree.Path, item btrfstree.Item) error { + 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 @@ -224,11 +206,11 @@ func (bt *OldRebuiltForrest) rawTreeWalk(ctx context.Context, treeID btrfsprim.O Node: curNode, Slot: path.Node(-1).FromItemSlot, }) - return nil }, } + cbs.BadItem = cbs.Item - tree.TreeWalk(ctx, errHandle, cbs) + tree.TreeWalk(ctx, cbs) } func (tree oldRebuiltTree) addErrs(fn func(btrfsprim.Key, uint32) int, err error) error { @@ -358,6 +340,8 @@ 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 { @@ -370,11 +354,11 @@ func (bt *OldRebuiltForrest) TreeWalk(ctx context.Context, treeID btrfsprim.ObjI }) return } - tree.treeWalk(ctx, errHandle, cbs) + tree.treeWalk(ctx, cbs) } -func (tree oldRebuiltTree) treeWalk(ctx context.Context, errHandle func(*btrfstree.TreeError), cbs btrfstree.TreeWalkHandler) { - if cbs.Item == nil { +func (tree oldRebuiltTree) treeWalk(ctx context.Context, cbs btrfstree.TreeWalkHandler) { + if cbs.Item == nil && cbs.BadItem == nil { return } var node *btrfstree.Node @@ -407,10 +391,17 @@ func (tree oldRebuiltTree) treeWalk(ctx context.Context, errHandle func(*btrfstr ToMaxKey: indexItem.Value.Key, }, } - if err := cbs.Item(itemPath, item); err != nil { - errHandle(&btrfstree.TreeError{Path: itemPath, Err: err}) + switch item.Body.(type) { + case *btrfsitem.Error: + if cbs.BadItem != nil { + cbs.BadItem(itemPath, item) + } + default: + if cbs.Item != nil { + cbs.Item(itemPath, item) + } } - return true + return ctx.Err() == nil }) node.Free() } diff --git a/lib/btrfsutil/walk.go b/lib/btrfsutil/walk.go index bbdf992..b05218c 100644 --- a/lib/btrfsutil/walk.go +++ b/lib/btrfsutil/walk.go @@ -61,7 +61,7 @@ func WalkAllTrees(ctx context.Context, fs btrfstree.TreeOperator, cbs WalkAllTre }, } origItem := cbs.Item - cbs.Item = func(path btrfstree.Path, item btrfstree.Item) error { + cbs.Item = func(path btrfstree.Path, item btrfstree.Item) { if item.Key.ItemType == btrfsitem.ROOT_ITEM_KEY { trees = append(trees, struct { Name string @@ -73,9 +73,8 @@ func WalkAllTrees(ctx context.Context, fs btrfstree.TreeOperator, cbs WalkAllTre }) } if origItem != nil { - return origItem(path, item) + origItem(path, item) } - return nil } for i := 0; i < len(trees); i++ { -- cgit v1.1-4-g5e80