summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
Diffstat
-rw-r--r--cmd/btrfs-rec/inspect/dumptrees/print_tree.go15
-rw-r--r--cmd/btrfs-rec/inspect/rebuildtrees/scan.go2
-rw-r--r--cmd/btrfs-rec/inspect_lstrees.go14
-rw-r--r--cmd/btrfs-rec/inspect_spewitems.go6
-rw-r--r--lib/btrfs/btrfstree/btree.go70
-rw-r--r--lib/btrfs/btrfstree/btree_forrest.go82
-rw-r--r--lib/btrfs/btrfstree/btree_tree.go622
-rw-r--r--lib/btrfs/io2_lv.go7
-rw-r--r--lib/btrfs/io3_btree.go5
-rw-r--r--lib/btrfsutil/graph.go14
-rw-r--r--lib/btrfsutil/old_rebuilt_forrest.go168
-rw-r--r--lib/btrfsutil/walk.go5
12 files changed, 435 insertions, 575 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/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/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 e91fcc1..bc1bac2 100644
--- a/lib/btrfs/btrfstree/btree.go
+++ b/lib/btrfs/btrfstree/btree.go
@@ -22,30 +22,51 @@ type TreeSearcher interface {
Search(key btrfsprim.Key, size uint32) int
}
+type TreeWalkHandler struct {
+ BadSuperblock func(error)
+
+ // Callbacks for entire nodes.
+ //
+ // 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.
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)
@@ -62,25 +83,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
diff --git a/lib/btrfs/btrfstree/btree_forrest.go b/lib/btrfs/btrfstree/btree_forrest.go
index 0f46d42..8f8e2de 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"
@@ -16,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
@@ -24,32 +25,32 @@ 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{
- 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,
@@ -65,7 +66,7 @@ func LookupTreeRoot(fs TreeOperator, sb Superblock, treeID btrfsprim.ObjID) (*Tr
switch rootItemBody := rootItem.Body.(type) {
case *btrfsitem.Root:
return &TreeRoot{
- TreeID: treeID,
+ ID: treeID,
RootNode: rootItemBody.ByteNr,
Level: rootItemBody.Level,
Generation: rootItemBody.Generation,
@@ -77,3 +78,70 @@ func LookupTreeRoot(fs TreeOperator, sb Superblock, treeID btrfsprim.ObjID) (*Tr
}
}
}
+
+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, 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
+ }
+
+ 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 459f481..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"
@@ -18,39 +16,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(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, cbs TreeWalkHandler) {
path := Path{{
- FromTree: rootInfo.TreeID,
+ 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, cbs)
}
-func (fs TreeOperatorImpl) treeWalk(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
}
@@ -58,442 +41,229 @@ func (fs TreeOperatorImpl) treeWalk(ctx context.Context, path Path, errHandle fu
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 := fs.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 {
- 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)
}
- fs.treeWalk(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
- }
+ default:
+ if cbs.Item != nil {
+ cbs.Item(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
- }
- }
- }
+ if ctx.Err() != nil {
+ return
}
}
- 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})
- }
+}
+
+// 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
+ }
+ 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 KeyPointer{}, false
}
-func (fs TreeOperatorImpl) treeSearch(treeRoot TreeRoot, fn func(btrfsprim.Key, uint32) int) (Path, *Node, error) {
- path := Path{{
- FromTree: treeRoot.TreeID,
- FromItemSlot: -1,
- ToNodeAddr: treeRoot.RootNode,
- ToNodeGeneration: treeRoot.Generation,
- ToNodeLevel: treeRoot.Level,
- ToMaxKey: btrfsprim.MaxKey,
- }}
- for {
- if path.Node(-1).ToNodeAddr == 0 {
- return nil, nil, ErrNoItem
- }
- node, err := fs.ReadNode(path)
- if err != nil {
- node.Free()
- return nil, nil, err
+func (tree *RawTree) TreeSearch(ctx context.Context, searcher TreeSearcher) (Item, error) {
+ ctx, cancel := context.WithCancel(ctx)
+ var retErr error
+ setErr := func(err error) {
+ if retErr == nil && err != nil {
+ retErr = fmt.Errorf("item with %s: %w", searcher, err)
}
+ cancel()
+ }
- 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()
+ 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 {
+ setErr(ErrNoItem)
+ return
+ }
+ selKP = kp
+ } else { // leaf node
+ slot, ok := slices.Search(node.BodyLeaf, func(item Item) int {
+ return searcher.Search(item.Key, item.BodySize)
+ })
+ if !ok {
+ setErr(ErrNoItem)
+ return
+ }
+ ret = node.BodyLeaf[slot]
+ ret.Body = ret.Body.CloneItem()
}
- 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
+ },
+ 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
+ },
+ })
- // 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
- }
- }
+ return ret, retErr
}
-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,
- })
- }
- }
- // 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
+func (tree *RawTree) TreeLookup(ctx context.Context, key btrfsprim.Key) (Item, error) {
+ return tree.TreeSearch(ctx, SearchExactKey(key))
}
-func (fs TreeOperatorImpl) next(path Path, node *Node) (Path, *Node, error) {
- var err error
- path = path.DeepCopy()
+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
- // 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
- }
- 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
+ var minKP btrfsprim.Key
+ var cnt int
+ tree.TreeWalk(ctx, TreeWalkHandler{
+ Node: func(_ Path, node *Node) {
+ // Only bother for interior nodes.
+ if node.Head.Level == 0 {
+ return
}
- 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
+ kp, ok := searchKP(node.BodyInterior, searcher.Search)
+ if !ok {
+ cancel()
+ return
}
- 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
+ minKP = kp.Key
+ },
+ 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 false
}
- 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()
+ if kp.Key.Compare(minKP) > 0 {
+ return false
}
- 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
-}
-
-// TreeSearch implements the 'TreeOperator' interface.
-func (fs TreeOperatorImpl) TreeSearch(treeID btrfsprim.ObjID, searcher TreeSearcher) (Item, error) {
- sb, err := fs.Superblock()
- if err != nil {
- return Item{}, err
- }
- rootInfo, err := LookupTreeRoot(fs, *sb, treeID)
- if err != nil {
- return Item{}, err
- }
- path, node, err := fs.treeSearch(*rootInfo, 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
-}
-
-// TreeLookup implements the 'TreeOperator' interface.
-func (fs TreeOperatorImpl) TreeLookup(treeID btrfsprim.ObjID, key btrfsprim.Key) (Item, error) {
- return fs.TreeSearch(treeID, SearchExactKey(key))
-}
-
-// TreeSearchAll implements the 'TreeOperator' interface.
-func (fs TreeOperatorImpl) TreeSearchAll(treeID btrfsprim.ObjID, searcher TreeSearcher) ([]Item, error) {
- sb, err := fs.Superblock()
- if err != nil {
- return nil, err
- }
- rootInfo, err := LookupTreeRoot(fs, *sb, treeID)
- if err != nil {
- return nil, err
- }
- middlePath, middleNode, err := fs.treeSearch(*rootInfo, searcher.Search)
- if err != nil {
- return nil, fmt.Errorf("items with %s: %w", searcher, err)
- }
- middleItem := middleNode.BodyLeaf[middlePath.Node(-1).FromItemSlot]
+ return true
+ },
+ Item: func(_ Path, item Item) {
+ 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()
+ }
+ },
+ BadItem: func(_ Path, item Item) {
+ 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()
+ }
+ },
+ })
- ret := []Item{middleItem}
- var errs derror.MultiError
- prevPath, prevNode := middlePath, middleNode
- for {
- prevPath, prevNode, err = fs.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 = fs.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 = fs.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)
+ 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
}
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/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..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"
@@ -20,6 +21,10 @@ import (
)
type oldRebuiltTree struct {
+ forrest *OldRebuiltForrest
+
+ ID btrfsprim.ObjID
+
RootErr error
Items *containers.RBTree[oldRebuiltTreeValue]
Errors *containers.IntervalTree[btrfsprim.Key, oldRebuiltTreeError]
@@ -114,7 +119,9 @@ func NewOldRebuiltForrest(ctx context.Context, inner *btrfs.FS) *OldRebuiltForre
}
}
-func (bt *OldRebuiltForrest) RebuiltTree(treeID btrfsprim.ObjID) oldRebuiltTree {
+// 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()
defer bt.rootTreeMu.Unlock()
@@ -133,9 +140,11 @@ 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)
+ cacheEntry.forrest = bt
+ cacheEntry.ID = treeID
+ dlog.Infof(ctx, "indexing tree %v...", treeID)
+ bt.rawTreeWalk(ctx, treeID, &cacheEntry)
+ dlog.Infof(ctx, "... done indexing tree %v", treeID)
if treeID == btrfsprim.ROOT_TREE_OBJECTID {
bt.rootTree = &cacheEntry
@@ -147,47 +156,33 @@ 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, *sb, treeID)
+ root, err := btrfstree.LookupTreeRoot(ctx, bt, *sb, treeID)
if err != nil {
cacheEntry.RootErr = err
return
}
-
- 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,
- })
+ tree := &btrfstree.RawTree{
+ Forrest: btrfstree.TreeOperatorImpl{NodeSource: bt.inner},
+ TreeRoot: *root,
}
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,
@@ -196,14 +191,13 @@ func (bt *OldRebuiltForrest) rawTreeWalk(treeID btrfsprim.ObjID, cacheEntry *old
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
// 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,
@@ -212,15 +206,11 @@ func (bt *OldRebuiltForrest) rawTreeWalk(treeID btrfsprim.ObjID, cacheEntry *old
Node: curNode,
Slot: path.Node(-1).FromItemSlot,
})
- return nil
},
}
+ cbs.BadItem = cbs.Item
- btrfstree.TreeOperatorImpl{NodeSource: bt.inner}.RawTreeWalk(bt.ctx, *root, errHandle, cbs)
-}
-
-func (bt *OldRebuiltForrest) TreeLookup(treeID btrfsprim.ObjID, key btrfsprim.Key) (btrfstree.Item, error) {
- return bt.TreeSearch(treeID, btrfstree.SearchExactKey(key))
+ tree.TreeWalk(ctx, cbs)
}
func (tree oldRebuiltTree) addErrs(fn func(btrfsprim.Key, uint32) int, err error) error {
@@ -267,8 +257,22 @@ func (bt *OldRebuiltForrest) readNode(nodeInfo nodeInfo) *btrfstree.Node {
return node
}
+// TreeLookup implements btrfstree.TreeOperator.
+func (bt *OldRebuiltForrest) TreeLookup(treeID btrfsprim.ObjID, key btrfsprim.Key) (btrfstree.Item, error) {
+ return bt.RebuiltTree(bt.ctx, treeID).treeLookup(bt.ctx, key)
+}
+
+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(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
}
@@ -280,7 +284,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]
@@ -291,46 +295,55 @@ 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(treeID)
+ tree := bt.RebuiltTree(bt.ctx, treeID)
if tree.RootErr != nil {
return nil, tree.RootErr
}
- var indexItems []oldRebuiltTreeValue
+ 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(node *containers.RBNode[oldRebuiltTreeValue]) bool {
- indexItems = append(indexItems, node.Value)
- return true
+ func(rbNode *containers.RBNode[oldRebuiltTreeValue]) bool {
+ cnt++
+ if node == nil || node.Head.Addr != rbNode.Value.Node.LAddr {
+ node.Free()
+ node = tree.forrest.readNode(rbNode.Value.Node)
+ }
+ return handleFn(node.BodyLeaf[rbNode.Value.Slot])
})
- 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 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
}
+// 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(treeID)
+ tree := bt.RebuiltTree(ctx, treeID)
if tree.RootErr != nil {
errHandle(&btrfstree.TreeError{
Path: btrfstree.Path{{
@@ -341,7 +354,11 @@ func (bt *OldRebuiltForrest) TreeWalk(ctx context.Context, treeID btrfsprim.ObjI
})
return
}
- if cbs.Item == nil {
+ tree.treeWalk(ctx, cbs)
+}
+
+func (tree oldRebuiltTree) treeWalk(ctx context.Context, cbs btrfstree.TreeWalkHandler) {
+ if cbs.Item == nil && cbs.BadItem == nil {
return
}
var node *btrfstree.Node
@@ -349,18 +366,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,
@@ -374,18 +391,27 @@ func (bt *OldRebuiltForrest) TreeWalk(ctx context.Context, treeID btrfsprim.ObjI
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()
}
+// 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)
}
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++ {
generated by cgit v1.2.3-54-g00ecf (git 2.45.2) at 2024-11-09 05:15:42 +0000