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 --- lib/btrfs/btrfstree/btree_forrest.go | 3 ++- lib/btrfs/btrfstree/btree_tree.go | 8 +++++--- 2 files changed, 7 insertions(+), 4 deletions(-) (limited to 'lib/btrfs') 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 } -- cgit v1.2.3-2-g168b 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(-) (limited to 'lib/btrfs') 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.2.3-2-g168b 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 ++-- 2 files changed, 8 insertions(+), 8 deletions(-) (limited to 'lib/btrfs') 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, -- cgit v1.2.3-2-g168b 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 +++++++++++------------------------- 2 files changed, 86 insertions(+), 63 deletions(-) (limited to 'lib/btrfs') 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 -- cgit v1.2.3-2-g168b 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(-) (limited to 'lib/btrfs') 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.2.3-2-g168b 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(-) (limited to 'lib/btrfs') 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.2.3-2-g168b 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 --- 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 +- 5 files changed, 133 insertions(+), 162 deletions(-) (limited to 'lib/btrfs') 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 }, }, ) -- cgit v1.2.3-2-g168b