summaryrefslogtreecommitdiff
path: root/lib
diff options
context:
space:
mode:
Diffstat (limited to 'lib')
-rw-r--r--lib/btrfs/btrfsitem/item_chunk.go5
-rw-r--r--lib/btrfs/btrfstree/btree.go22
-rw-r--r--lib/btrfs/btrfstree/btree_tree.go210
-rw-r--r--lib/btrfs/btrfstree/path.go22
-rw-r--r--lib/btrfs/btrfstree/readnode.go16
-rw-r--r--lib/btrfs/btrfstree/types_node.go93
-rw-r--r--lib/btrfs/io2_lv.go2
-rw-r--r--lib/btrfs/io3_btree.go6
-rw-r--r--lib/btrfs/io4_fs.go83
-rw-r--r--lib/btrfsutil/graph.go38
-rw-r--r--lib/btrfsutil/listnodes.go5
-rw-r--r--lib/btrfsutil/old_rebuilt_forrest.go260
-rw-r--r--lib/btrfsutil/print_addrspace.go73
-rw-r--r--lib/btrfsutil/rebuilt_forrest.go144
-rw-r--r--lib/btrfsutil/rebuilt_readitem.go130
-rw-r--r--lib/btrfsutil/rebuilt_tree.go60
-rw-r--r--lib/btrfsutil/scan.go9
-rw-r--r--lib/btrfsutil/skinny_paths.go146
-rw-r--r--lib/btrfsutil/walk.go4
-rw-r--r--lib/containers/optional.go13
-rw-r--r--lib/diskio/file_iface.go8
21 files changed, 585 insertions, 764 deletions
diff --git a/lib/btrfs/btrfsitem/item_chunk.go b/lib/btrfs/btrfsitem/item_chunk.go
index 607df75..9bdef1f 100644
--- a/lib/btrfs/btrfsitem/item_chunk.go
+++ b/lib/btrfs/btrfsitem/item_chunk.go
@@ -61,10 +61,7 @@ func (chunk Chunk) Mappings(key btrfsprim.Key) []btrfsvol.Mapping {
},
Size: chunk.Head.Size,
SizeLocked: true,
- Flags: containers.Optional[btrfsvol.BlockGroupFlags]{
- OK: true,
- Val: chunk.Head.Type,
- },
+ Flags: containers.OptionalValue(chunk.Head.Type),
})
}
return ret
diff --git a/lib/btrfs/btrfstree/btree.go b/lib/btrfs/btrfstree/btree.go
index 89d4f9d..e91fcc1 100644
--- a/lib/btrfs/btrfstree/btree.go
+++ b/lib/btrfs/btrfstree/btree.go
@@ -11,8 +11,6 @@ import (
"fmt"
"git.lukeshu.com/btrfs-progs-ng/lib/btrfs/btrfsprim"
- "git.lukeshu.com/btrfs-progs-ng/lib/btrfs/btrfsvol"
- "git.lukeshu.com/btrfs-progs-ng/lib/diskio"
)
type TreeSearcher interface {
@@ -71,20 +69,20 @@ type TreeWalkHandler struct {
// 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(TreePath) error
- Node func(TreePath, *diskio.Ref[btrfsvol.LogicalAddr, Node]) error
- BadNode func(TreePath, *diskio.Ref[btrfsvol.LogicalAddr, Node], error) error
- PostNode func(TreePath, *diskio.Ref[btrfsvol.LogicalAddr, Node]) error
+ 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(TreePath, KeyPointer) error
- PostKeyPointer func(TreePath, KeyPointer) error
+ PreKeyPointer func(Path, KeyPointer) error
+ PostKeyPointer func(Path, KeyPointer) error
// Callbacks for items on leaf nodes
- Item func(TreePath, Item) error
- BadItem func(TreePath, Item) error
+ Item func(Path, Item) error
+ BadItem func(Path, Item) error
}
type TreeError struct {
- Path TreePath
+ Path Path
Err error
}
@@ -96,5 +94,5 @@ func (e *TreeError) Error() string {
type NodeSource interface {
Superblock() (*Superblock, error)
- ReadNode(TreePath) (*diskio.Ref[btrfsvol.LogicalAddr, Node], error)
+ ReadNode(Path) (*Node, error)
}
diff --git a/lib/btrfs/btrfstree/btree_tree.go b/lib/btrfs/btrfstree/btree_tree.go
index 1e3c789..459f481 100644
--- a/lib/btrfs/btrfstree/btree_tree.go
+++ b/lib/btrfs/btrfstree/btree_tree.go
@@ -15,8 +15,6 @@ import (
"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/btrfsvol"
- "git.lukeshu.com/btrfs-progs-ng/lib/diskio"
"git.lukeshu.com/btrfs-progs-ng/lib/slices"
)
@@ -28,11 +26,11 @@ type TreeOperatorImpl struct {
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: TreePath{{FromTree: treeID, ToMaxKey: btrfsprim.MaxKey}}, Err: err})
+ errHandle(&TreeError{Path: Path{{FromTree: treeID, ToMaxKey: btrfsprim.MaxKey}}, Err: err})
}
rootInfo, err := LookupTreeRoot(fs, *sb, treeID)
if err != nil {
- errHandle(&TreeError{Path: TreePath{{FromTree: treeID, ToMaxKey: btrfsprim.MaxKey}}, Err: err})
+ errHandle(&TreeError{Path: Path{{FromTree: treeID, ToMaxKey: btrfsprim.MaxKey}}, Err: err})
return
}
fs.RawTreeWalk(ctx, *rootInfo, errHandle, cbs)
@@ -41,7 +39,7 @@ func (fs TreeOperatorImpl) TreeWalk(ctx context.Context, treeID btrfsprim.ObjID,
// 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) {
- path := TreePath{{
+ path := Path{{
FromTree: rootInfo.TreeID,
FromItemSlot: -1,
ToNodeAddr: rootInfo.RootNode,
@@ -52,7 +50,7 @@ func (fs TreeOperatorImpl) RawTreeWalk(ctx context.Context, rootInfo TreeRoot, e
fs.treeWalk(ctx, path, errHandle, cbs)
}
-func (fs TreeOperatorImpl) treeWalk(ctx context.Context, path TreePath, errHandle func(*TreeError), cbs TreeWalkHandler) {
+func (fs TreeOperatorImpl) treeWalk(ctx context.Context, path Path, errHandle func(*TreeError), cbs TreeWalkHandler) {
if ctx.Err() != nil {
return
}
@@ -72,7 +70,7 @@ func (fs TreeOperatorImpl) treeWalk(ctx context.Context, path TreePath, errHandl
}
}
node, err := fs.ReadNode(path)
- defer FreeNodeRef(node)
+ defer node.Free()
if ctx.Err() != nil {
return
}
@@ -97,17 +95,17 @@ func (fs TreeOperatorImpl) treeWalk(ctx context.Context, path TreePath, errHandl
return
}
if node != nil {
- for i, item := range node.Data.BodyInterior {
+ for i, item := range node.BodyInterior {
toMaxKey := path.Node(-1).ToMaxKey
- if i+1 < len(node.Data.BodyInterior) {
- toMaxKey = node.Data.BodyInterior[i+1].Key.Mm()
+ if i+1 < len(node.BodyInterior) {
+ toMaxKey = node.BodyInterior[i+1].Key.Mm()
}
- itemPath := append(path, TreePathElem{
- FromTree: node.Data.Head.Owner,
+ itemPath := append(path, PathElem{
+ FromTree: node.Head.Owner,
FromItemSlot: i,
ToNodeAddr: item.BlockPtr,
ToNodeGeneration: item.Generation,
- ToNodeLevel: node.Data.Head.Level - 1,
+ ToNodeLevel: node.Head.Level - 1,
ToKey: item.Key,
ToMaxKey: toMaxKey,
})
@@ -129,9 +127,9 @@ func (fs TreeOperatorImpl) treeWalk(ctx context.Context, path TreePath, errHandl
}
}
}
- for i, item := range node.Data.BodyLeaf {
- itemPath := append(path, TreePathElem{
- FromTree: node.Data.Head.Owner,
+ for i, item := range node.BodyLeaf {
+ itemPath := append(path, PathElem{
+ FromTree: node.Head.Owner,
FromItemSlot: i,
ToKey: item.Key,
ToMaxKey: item.Key,
@@ -169,8 +167,8 @@ func (fs TreeOperatorImpl) treeWalk(ctx context.Context, path TreePath, errHandl
}
}
-func (fs TreeOperatorImpl) treeSearch(treeRoot TreeRoot, fn func(btrfsprim.Key, uint32) int) (TreePath, *diskio.Ref[btrfsvol.LogicalAddr, Node], error) {
- path := TreePath{{
+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,
@@ -184,15 +182,15 @@ func (fs TreeOperatorImpl) treeSearch(treeRoot TreeRoot, fn func(btrfsprim.Key,
}
node, err := fs.ReadNode(path)
if err != nil {
- FreeNodeRef(node)
+ node.Free()
return nil, nil, err
}
switch {
- case node.Data.Head.Level > 0:
+ case node.Head.Level > 0:
// interior node
- // Search for the right-most node.Data.BodyInterior item for which
+ // Search for the right-most node.BodyInterior item for which
// `fn(item.Key) >= 0`.
//
// + + + + 0 - - - -
@@ -200,31 +198,31 @@ func (fs TreeOperatorImpl) treeSearch(treeRoot TreeRoot, fn func(btrfsprim.Key,
// 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.Data.BodyInterior, func(kp KeyPointer) int {
+ 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 {
- FreeNodeRef(node)
+ node.Free()
return nil, nil, ErrNoItem
}
toMaxKey := path.Node(-1).ToMaxKey
- if lastGood+1 < len(node.Data.BodyInterior) {
- toMaxKey = node.Data.BodyInterior[lastGood+1].Key.Mm()
+ if lastGood+1 < len(node.BodyInterior) {
+ toMaxKey = node.BodyInterior[lastGood+1].Key.Mm()
}
- path = append(path, TreePathElem{
- FromTree: node.Data.Head.Owner,
+ path = append(path, PathElem{
+ FromTree: node.Head.Owner,
FromItemSlot: lastGood,
- ToNodeAddr: node.Data.BodyInterior[lastGood].BlockPtr,
- ToNodeGeneration: node.Data.BodyInterior[lastGood].Generation,
- ToNodeLevel: node.Data.Head.Level - 1,
- ToKey: node.Data.BodyInterior[lastGood].Key,
+ ToNodeAddr: node.BodyInterior[lastGood].BlockPtr,
+ ToNodeGeneration: node.BodyInterior[lastGood].Generation,
+ ToNodeLevel: node.Head.Level - 1,
+ ToKey: node.BodyInterior[lastGood].Key,
ToMaxKey: toMaxKey,
})
- FreeNodeRef(node)
+ node.Free()
default:
// leaf node
- // Search for a member of node.Data.BodyLeaf for which
+ // Search for a member of node.BodyLeaf for which
// `fn(item.Head.Key) == 0`.
//
// + + + + 0 - - - -
@@ -234,25 +232,25 @@ func (fs TreeOperatorImpl) treeSearch(treeRoot TreeRoot, fn func(btrfsprim.Key,
// is returned.
//
// Implement this search as a binary search.
- slot, ok := slices.Search(node.Data.BodyLeaf, func(item Item) int {
+ slot, ok := slices.Search(node.BodyLeaf, func(item Item) int {
return fn(item.Key, item.BodySize)
})
if !ok {
- FreeNodeRef(node)
+ node.Free()
return nil, nil, ErrNoItem
}
- path = append(path, TreePathElem{
- FromTree: node.Data.Head.Owner,
+ path = append(path, PathElem{
+ FromTree: node.Head.Owner,
FromItemSlot: slot,
- ToKey: node.Data.BodyLeaf[slot].Key,
- ToMaxKey: node.Data.BodyLeaf[slot].Key,
+ ToKey: node.BodyLeaf[slot].Key,
+ ToMaxKey: node.BodyLeaf[slot].Key,
})
return path, node, nil
}
}
}
-func (fs TreeOperatorImpl) prev(path TreePath, node *diskio.Ref[btrfsvol.LogicalAddr, Node]) (TreePath, *diskio.Ref[btrfsvol.LogicalAddr, Node], error) {
+func (fs TreeOperatorImpl) prev(path Path, node *Node) (Path, *Node, error) {
var err error
path = path.DeepCopy()
@@ -266,139 +264,139 @@ func (fs TreeOperatorImpl) prev(path TreePath, node *diskio.Ref[btrfsvol.Logical
// go left
path.Node(-1).FromItemSlot--
if path.Node(-1).ToNodeAddr != 0 {
- if node.Addr != path.Node(-2).ToNodeAddr {
- FreeNodeRef(node)
+ if node.Head.Addr != path.Node(-2).ToNodeAddr {
+ node.Free()
node, err = fs.ReadNode(path.Parent())
if err != nil {
- FreeNodeRef(node)
+ node.Free()
return nil, nil, err
}
- path.Node(-1).ToNodeAddr = node.Data.BodyInterior[path.Node(-1).FromItemSlot].BlockPtr
+ path.Node(-1).ToNodeAddr = node.BodyInterior[path.Node(-1).FromItemSlot].BlockPtr
}
}
// go down
for path.Node(-1).ToNodeAddr != 0 {
- if node.Addr != path.Node(-1).ToNodeAddr {
- FreeNodeRef(node)
+ if node.Head.Addr != path.Node(-1).ToNodeAddr {
+ node.Free()
node, err = fs.ReadNode(path)
if err != nil {
- FreeNodeRef(node)
+ node.Free()
return nil, nil, err
}
}
- if node.Data.Head.Level > 0 {
- path = append(path, TreePathElem{
- FromTree: node.Data.Head.Owner,
- FromItemSlot: len(node.Data.BodyInterior) - 1,
- ToNodeAddr: node.Data.BodyInterior[len(node.Data.BodyInterior)-1].BlockPtr,
- ToNodeGeneration: node.Data.BodyInterior[len(node.Data.BodyInterior)-1].Generation,
- ToNodeLevel: node.Data.Head.Level - 1,
- ToKey: node.Data.BodyInterior[len(node.Data.BodyInterior)-1].Key,
+ 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, TreePathElem{
- FromTree: node.Data.Head.Owner,
- FromItemSlot: len(node.Data.BodyLeaf) - 1,
- ToKey: node.Data.BodyLeaf[len(node.Data.BodyLeaf)-1].Key,
- ToMaxKey: node.Data.BodyLeaf[len(node.Data.BodyLeaf)-1].Key,
+ 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.Addr != path.Node(-2).ToNodeAddr {
- FreeNodeRef(node)
+ if node.Head.Addr != path.Node(-2).ToNodeAddr {
+ node.Free()
node, err = fs.ReadNode(path.Parent())
if err != nil {
- FreeNodeRef(node)
+ node.Free()
return nil, nil, err
}
}
return path, node, nil
}
-func (fs TreeOperatorImpl) next(path TreePath, node *diskio.Ref[btrfsvol.LogicalAddr, Node]) (TreePath, *diskio.Ref[btrfsvol.LogicalAddr, Node], error) {
+func (fs TreeOperatorImpl) next(path Path, node *Node) (Path, *Node, error) {
var err error
path = path.DeepCopy()
// go up
- if node.Addr != path.Node(-2).ToNodeAddr {
- FreeNodeRef(node)
+ if node.Head.Addr != path.Node(-2).ToNodeAddr {
+ node.Free()
node, err = fs.ReadNode(path.Parent())
if err != nil {
- FreeNodeRef(node)
+ node.Free()
return nil, nil, err
}
- path.Node(-2).ToNodeLevel = node.Data.Head.Level
+ path.Node(-2).ToNodeLevel = node.Head.Level
}
- for path.Node(-1).FromItemSlot+1 >= int(node.Data.Head.NumItems) {
+ for path.Node(-1).FromItemSlot+1 >= int(node.Head.NumItems) {
path = path.Parent()
if len(path) == 1 {
return nil, nil, nil
}
- if node.Addr != path.Node(-2).ToNodeAddr {
- FreeNodeRef(node)
+ if node.Head.Addr != path.Node(-2).ToNodeAddr {
+ node.Free()
node, err = fs.ReadNode(path.Parent())
if err != nil {
- FreeNodeRef(node)
+ node.Free()
return nil, nil, err
}
- path.Node(-2).ToNodeLevel = node.Data.Head.Level
+ path.Node(-2).ToNodeLevel = node.Head.Level
}
}
// go right
path.Node(-1).FromItemSlot++
if path.Node(-1).ToNodeAddr != 0 {
- if node.Addr != path.Node(-2).ToNodeAddr {
- FreeNodeRef(node)
+ if node.Head.Addr != path.Node(-2).ToNodeAddr {
+ node.Free()
node, err = fs.ReadNode(path.Parent())
if err != nil {
- FreeNodeRef(node)
+ node.Free()
return nil, nil, err
}
- path.Node(-1).ToNodeAddr = node.Data.BodyInterior[path.Node(-1).FromItemSlot].BlockPtr
+ path.Node(-1).ToNodeAddr = node.BodyInterior[path.Node(-1).FromItemSlot].BlockPtr
}
}
// go down
for path.Node(-1).ToNodeAddr != 0 {
- if node.Addr != path.Node(-1).ToNodeAddr {
- FreeNodeRef(node)
+ if node.Head.Addr != path.Node(-1).ToNodeAddr {
+ node.Free()
node, err = fs.ReadNode(path)
if err != nil {
- FreeNodeRef(node)
+ node.Free()
return nil, nil, err
}
- path.Node(-1).ToNodeLevel = node.Data.Head.Level
+ path.Node(-1).ToNodeLevel = node.Head.Level
}
- if node.Data.Head.Level > 0 {
+ if node.Head.Level > 0 {
toMaxKey := path.Node(-1).ToMaxKey
- if len(node.Data.BodyInterior) > 1 {
- toMaxKey = node.Data.BodyInterior[1].Key.Mm()
+ if len(node.BodyInterior) > 1 {
+ toMaxKey = node.BodyInterior[1].Key.Mm()
}
- path = append(path, TreePathElem{
- FromTree: node.Data.Head.Owner,
+ path = append(path, PathElem{
+ FromTree: node.Head.Owner,
FromItemSlot: 0,
- ToNodeAddr: node.Data.BodyInterior[0].BlockPtr,
- ToNodeGeneration: node.Data.BodyInterior[0].Generation,
- ToNodeLevel: node.Data.Head.Level - 1,
- ToKey: node.Data.BodyInterior[0].Key,
+ 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, TreePathElem{
- FromTree: node.Data.Head.Owner,
+ path = append(path, PathElem{
+ FromTree: node.Head.Owner,
FromItemSlot: 0,
- ToKey: node.Data.BodyInterior[0].Key,
- ToMaxKey: node.Data.BodyInterior[0].Key,
+ ToKey: node.BodyInterior[0].Key,
+ ToMaxKey: node.BodyInterior[0].Key,
})
}
}
// return
- if node.Addr != path.Node(-2).ToNodeAddr {
- FreeNodeRef(node)
+ if node.Head.Addr != path.Node(-2).ToNodeAddr {
+ node.Free()
node, err = fs.ReadNode(path.Parent())
if err != nil {
- FreeNodeRef(node)
+ node.Free()
return nil, nil, err
}
}
@@ -419,9 +417,9 @@ func (fs TreeOperatorImpl) TreeSearch(treeID btrfsprim.ObjID, searcher TreeSearc
if err != nil {
return Item{}, fmt.Errorf("item with %s: %w", searcher, err)
}
- item := node.Data.BodyLeaf[path.Node(-1).FromItemSlot]
+ item := node.BodyLeaf[path.Node(-1).FromItemSlot]
item.Body = item.Body.CloneItem()
- FreeNodeRef(node)
+ node.Free()
return item, nil
}
@@ -444,7 +442,7 @@ func (fs TreeOperatorImpl) TreeSearchAll(treeID btrfsprim.ObjID, searcher TreeSe
if err != nil {
return nil, fmt.Errorf("items with %s: %w", searcher, err)
}
- middleItem := middleNode.Data.BodyLeaf[middlePath.Node(-1).FromItemSlot]
+ middleItem := middleNode.BodyLeaf[middlePath.Node(-1).FromItemSlot]
ret := []Item{middleItem}
var errs derror.MultiError
@@ -458,7 +456,7 @@ func (fs TreeOperatorImpl) TreeSearchAll(treeID btrfsprim.ObjID, searcher TreeSe
if len(prevPath) == 0 {
break
}
- prevItem := prevNode.Data.BodyLeaf[prevPath.Node(-1).FromItemSlot]
+ prevItem := prevNode.BodyLeaf[prevPath.Node(-1).FromItemSlot]
if searcher.Search(prevItem.Key, prevItem.BodySize) != 0 {
break
}
@@ -467,11 +465,11 @@ func (fs TreeOperatorImpl) TreeSearchAll(treeID btrfsprim.ObjID, searcher TreeSe
ret = append(ret, item)
}
slices.Reverse(ret)
- if prevNode.Addr != middlePath.Node(-1).ToNodeAddr {
- FreeNodeRef(prevNode)
+ if prevNode.Head.Addr != middlePath.Node(-1).ToNodeAddr {
+ prevNode.Free()
middleNode, err = fs.ReadNode(middlePath)
if err != nil {
- FreeNodeRef(middleNode)
+ middleNode.Free()
return nil, fmt.Errorf("items with %s: %w", searcher, err)
}
}
@@ -485,7 +483,7 @@ func (fs TreeOperatorImpl) TreeSearchAll(treeID btrfsprim.ObjID, searcher TreeSe
if len(nextPath) == 0 {
break
}
- nextItem := nextNode.Data.BodyLeaf[nextPath.Node(-1).FromItemSlot]
+ nextItem := nextNode.BodyLeaf[nextPath.Node(-1).FromItemSlot]
if searcher.Search(nextItem.Key, nextItem.BodySize) != 0 {
break
}
@@ -493,7 +491,7 @@ func (fs TreeOperatorImpl) TreeSearchAll(treeID btrfsprim.ObjID, searcher TreeSe
item.Body = item.Body.CloneItem()
ret = append(ret, item)
}
- FreeNodeRef(nextNode)
+ nextNode.Free()
if errs != nil {
err = errs
}
diff --git a/lib/btrfs/btrfstree/path.go b/lib/btrfs/btrfstree/path.go
index b9ab5bc..c07d8a0 100644
--- a/lib/btrfs/btrfstree/path.go
+++ b/lib/btrfs/btrfstree/path.go
@@ -13,7 +13,7 @@ import (
"git.lukeshu.com/btrfs-progs-ng/lib/btrfs/btrfsvol"
)
-// TreePath is a path from the superblock (i.e. the root of the btrfs
+// Path is a path from the superblock (i.e. the root of the btrfs
// system) to the a node or item within one of the btrees in the
// system.
//
@@ -61,10 +61,10 @@ import (
// | <--------------- pathElem={from_tree:A, from_slot:1,
// | to_addr:0, to_gen: 0, to_lvl:0}
// [item]
-type TreePath []TreePathElem
+type Path []PathElem
-// A TreePathElem essentially represents a KeyPointer.
-type TreePathElem struct {
+// A PathElem essentially represents a KeyPointer.
+type PathElem struct {
// FromTree is the owning tree ID of the parent node; or the
// well-known tree ID if this is the root.
FromTree btrfsprim.ObjID
@@ -94,17 +94,17 @@ type TreePathElem struct {
ToMaxKey btrfsprim.Key
}
-func (elem TreePathElem) writeNodeTo(w io.Writer) {
+func (elem PathElem) writeNodeTo(w io.Writer) {
fmt.Fprintf(w, "node:%d@%v", elem.ToNodeLevel, elem.ToNodeAddr)
}
-func (path TreePath) String() string {
+func (path Path) String() string {
if len(path) == 0 {
return "(empty-path)"
}
var ret strings.Builder
fmt.Fprintf(&ret, "%s->", path[0].FromTree.Format(btrfsprim.ROOT_TREE_OBJECTID))
- if len(path) == 1 && path[0] == (TreePathElem{FromTree: path[0].FromTree, FromItemSlot: -1}) {
+ if len(path) == 1 && path[0] == (PathElem{FromTree: path[0].FromTree, FromItemSlot: -1}) {
ret.WriteString("(empty-path)")
} else {
path[0].writeNodeTo(&ret)
@@ -119,11 +119,11 @@ func (path TreePath) String() string {
return ret.String()
}
-func (path TreePath) DeepCopy() TreePath {
- return append(TreePath(nil), path...)
+func (path Path) DeepCopy() Path {
+ return append(Path(nil), path...)
}
-func (path TreePath) Parent() TreePath {
+func (path Path) Parent() Path {
return path[:len(path)-1]
}
@@ -131,7 +131,7 @@ func (path TreePath) Parent() TreePath {
// `&path[x]`, but negative values of x move down from the end of path
// (similar to how lists work in many other languages, such as
// Python).
-func (path TreePath) Node(x int) *TreePathElem {
+func (path Path) Node(x int) *PathElem {
if x < 0 {
x += len(path)
}
diff --git a/lib/btrfs/btrfstree/readnode.go b/lib/btrfs/btrfstree/readnode.go
index 4ccc17b..c2e3b0f 100644
--- a/lib/btrfs/btrfstree/readnode.go
+++ b/lib/btrfs/btrfstree/readnode.go
@@ -1,4 +1,4 @@
-// Copyright (C) 2022 Luke Shumaker <lukeshu@lukeshu.com>
+// Copyright (C) 2022-2023 Luke Shumaker <lukeshu@lukeshu.com>
//
// SPDX-License-Identifier: GPL-2.0-or-later
@@ -33,8 +33,8 @@ type NodeFile interface {
// 'NodeSource' interface.
func FSReadNode(
fs NodeFile,
- path TreePath,
-) (*diskio.Ref[btrfsvol.LogicalAddr, Node], error) {
+ path Path,
+) (*Node, error) {
sb, err := fs.Superblock()
if err != nil {
return nil, fmt.Errorf("btrfs.FS.ReadNode: %w", err)
@@ -63,11 +63,11 @@ func FSReadNode(
}
return ReadNode[btrfsvol.LogicalAddr](fs, *sb, path.Node(-1).ToNodeAddr, NodeExpectations{
- LAddr: containers.Optional[btrfsvol.LogicalAddr]{OK: true, Val: path.Node(-1).ToNodeAddr},
- Level: containers.Optional[uint8]{OK: true, Val: path.Node(-1).ToNodeLevel},
- Generation: containers.Optional[btrfsprim.Generation]{OK: true, Val: path.Node(-1).ToNodeGeneration},
+ LAddr: containers.OptionalValue(path.Node(-1).ToNodeAddr),
+ Level: containers.OptionalValue(path.Node(-1).ToNodeLevel),
+ Generation: containers.OptionalValue(path.Node(-1).ToNodeGeneration),
Owner: checkOwner,
- MinItem: containers.Optional[btrfsprim.Key]{OK: true, Val: path.Node(-1).ToKey},
- MaxItem: containers.Optional[btrfsprim.Key]{OK: true, Val: path.Node(-1).ToMaxKey},
+ MinItem: containers.OptionalValue(path.Node(-1).ToKey),
+ MaxItem: containers.OptionalValue(path.Node(-1).ToMaxKey),
})
}
diff --git a/lib/btrfs/btrfstree/types_node.go b/lib/btrfs/btrfstree/types_node.go
index 8295ccb..622f23c 100644
--- a/lib/btrfs/btrfstree/types_node.go
+++ b/lib/btrfs/btrfstree/types_node.go
@@ -8,7 +8,6 @@ import (
"encoding/binary"
"errors"
"fmt"
- "unsafe"
"git.lukeshu.com/go/typedsync"
"github.com/datawire/dlib/derror"
@@ -308,12 +307,16 @@ type ItemHeader struct {
var itemPool containers.SlicePool[Item]
func (node *Node) Free() {
+ if node == nil {
+ return
+ }
for i := range node.BodyLeaf {
node.BodyLeaf[i].Body.Free()
node.BodyLeaf[i] = Item{}
}
itemPool.Put(node.BodyLeaf)
*node = Node{}
+ nodePool.Put(node)
}
func (node *Node) unmarshalLeaf(bodyBuf []byte) (int, error) {
@@ -440,32 +443,19 @@ func (e *IOError) Unwrap() error { return e.Err }
var bytePool containers.SlicePool[byte]
-var nodePool = typedsync.Pool[*diskio.Ref[int64, Node]]{
- New: func() *diskio.Ref[int64, Node] {
- return new(diskio.Ref[int64, Node])
+var nodePool = typedsync.Pool[*Node]{
+ New: func() *Node {
+ return new(Node)
},
}
-func FreeNodeRef[Addr ~int64](ref *diskio.Ref[Addr, Node]) {
- if ref == nil {
- return
- }
- ref.Data.Free()
- nodePool.Put((*diskio.Ref[int64, Node])(unsafe.Pointer(ref))) //nolint:gosec // I know it's unsafe.
-}
-
-func newNodeRef[Addr ~int64]() *diskio.Ref[Addr, Node] {
- ret, _ := nodePool.Get()
- return (*diskio.Ref[Addr, Node])(unsafe.Pointer(ret)) //nolint:gosec // I know it's unsafe.
-}
-
// ReadNode reads a node from the given file.
//
// It is possible that both a non-nil diskio.Ref and an error are
// returned. The error returned (if non-nil) is always of type
// *NodeError[Addr]. Notable errors that may be inside of the
// NodeError are ErrNotANode and *IOError.
-func ReadNode[Addr ~int64](fs diskio.File[Addr], sb Superblock, addr Addr, exp NodeExpectations) (*diskio.Ref[Addr, Node], error) {
+func ReadNode[Addr ~int64](fs diskio.ReaderAt[Addr], sb Superblock, addr Addr, exp NodeExpectations) (*Node, error) {
if int(sb.NodeSize) < nodeHeaderSize {
return nil, &NodeError[Addr]{
Op: "btrfstree.ReadNode", NodeAddr: addr,
@@ -481,16 +471,10 @@ func ReadNode[Addr ~int64](fs diskio.File[Addr], sb Superblock, addr Addr, exp N
// parse (early)
- nodeRef := newNodeRef[Addr]()
- *nodeRef = diskio.Ref[Addr, Node]{
- File: fs,
- Addr: addr,
- Data: Node{
- Size: sb.NodeSize,
- ChecksumType: sb.ChecksumType,
- },
- }
- if _, err := binstruct.Unmarshal(nodeBuf, &nodeRef.Data.Head); err != nil {
+ node, _ := nodePool.Get()
+ node.Size = sb.NodeSize
+ node.ChecksumType = sb.ChecksumType
+ if _, err := binstruct.Unmarshal(nodeBuf, &node.Head); err != nil {
// If there are enough bytes there (and we checked
// that above), then it shouldn't be possible for this
// unmarshal to fail.
@@ -499,20 +483,20 @@ func ReadNode[Addr ~int64](fs diskio.File[Addr], sb Superblock, addr Addr, exp N
// sanity checking (that prevents the main parse)
- if nodeRef.Data.Head.MetadataUUID != sb.EffectiveMetadataUUID() {
+ if node.Head.MetadataUUID != sb.EffectiveMetadataUUID() {
bytePool.Put(nodeBuf)
- return nodeRef, &NodeError[Addr]{Op: "btrfstree.ReadNode", NodeAddr: addr, Err: ErrNotANode}
+ return node, &NodeError[Addr]{Op: "btrfstree.ReadNode", NodeAddr: addr, Err: ErrNotANode}
}
- stored := nodeRef.Data.Head.Checksum
- calced, err := nodeRef.Data.ChecksumType.Sum(nodeBuf[csumSize:])
+ stored := node.Head.Checksum
+ calced, err := node.ChecksumType.Sum(nodeBuf[csumSize:])
if err != nil {
bytePool.Put(nodeBuf)
- return nodeRef, &NodeError[Addr]{Op: "btrfstree.ReadNode", NodeAddr: addr, Err: err}
+ return node, &NodeError[Addr]{Op: "btrfstree.ReadNode", NodeAddr: addr, Err: err}
}
if stored != calced {
bytePool.Put(nodeBuf)
- return nodeRef, &NodeError[Addr]{
+ return node, &NodeError[Addr]{
Op: "btrfstree.ReadNode", NodeAddr: addr,
Err: fmt.Errorf("looks like a node but is corrupt: checksum mismatch: stored=%v calculated=%v",
stored, calced),
@@ -530,50 +514,57 @@ func ReadNode[Addr ~int64](fs diskio.File[Addr], sb Superblock, addr Addr, exp N
// garbage data that is was never a valid node, so parsing it
// isn't useful.
- if _, err := binstruct.Unmarshal(nodeBuf, &nodeRef.Data); err != nil {
+ if _, err := binstruct.Unmarshal(nodeBuf, node); err != nil {
bytePool.Put(nodeBuf)
- return nodeRef, &NodeError[Addr]{Op: "btrfstree.ReadNode", NodeAddr: addr, Err: err}
+ return node, &NodeError[Addr]{Op: "btrfstree.ReadNode", NodeAddr: addr, Err: err}
}
bytePool.Put(nodeBuf)
// sanity checking (that doesn't prevent parsing)
+ if err := exp.Check(node); err != nil {
+ return node, &NodeError[Addr]{Op: "btrfstree.ReadNode", NodeAddr: addr, Err: err}
+ }
+
+ // return
+
+ return node, nil
+}
+
+func (exp NodeExpectations) Check(node *Node) error {
var errs derror.MultiError
- if exp.LAddr.OK && nodeRef.Data.Head.Addr != exp.LAddr.Val {
+ if exp.LAddr.OK && node.Head.Addr != exp.LAddr.Val {
errs = append(errs, fmt.Errorf("read from laddr=%v but claims to be at laddr=%v",
- exp.LAddr.Val, nodeRef.Data.Head.Addr))
+ exp.LAddr.Val, node.Head.Addr))
}
- if exp.Level.OK && nodeRef.Data.Head.Level != exp.Level.Val {
+ if exp.Level.OK && node.Head.Level != exp.Level.Val {
errs = append(errs, fmt.Errorf("expected level=%v but claims to be level=%v",
- exp.Level.Val, nodeRef.Data.Head.Level))
+ exp.Level.Val, node.Head.Level))
}
- if exp.Generation.OK && nodeRef.Data.Head.Generation != exp.Generation.Val {
+ if exp.Generation.OK && node.Head.Generation != exp.Generation.Val {
errs = append(errs, fmt.Errorf("expected generation=%v but claims to be generation=%v",
- exp.Generation.Val, nodeRef.Data.Head.Generation))
+ exp.Generation.Val, node.Head.Generation))
}
if exp.Owner != nil {
- if err := exp.Owner(nodeRef.Data.Head.Owner); err != nil {
+ if err := exp.Owner(node.Head.Owner); err != nil {
errs = append(errs, err)
}
}
- if nodeRef.Data.Head.NumItems == 0 {
+ if node.Head.NumItems == 0 {
errs = append(errs, fmt.Errorf("has no items"))
} else {
- if minItem, _ := nodeRef.Data.MinItem(); exp.MinItem.OK && exp.MinItem.Val.Compare(minItem) > 0 {
+ if minItem, _ := node.MinItem(); exp.MinItem.OK && exp.MinItem.Val.Compare(minItem) > 0 {
errs = append(errs, fmt.Errorf("expected minItem>=%v but node has minItem=%v",
exp.MinItem, minItem))
}
- if maxItem, _ := nodeRef.Data.MaxItem(); exp.MaxItem.OK && exp.MaxItem.Val.Compare(maxItem) < 0 {
+ if maxItem, _ := node.MaxItem(); exp.MaxItem.OK && exp.MaxItem.Val.Compare(maxItem) < 0 {
errs = append(errs, fmt.Errorf("expected maxItem<=%v but node has maxItem=%v",
exp.MaxItem, maxItem))
}
}
if len(errs) > 0 {
- return nodeRef, &NodeError[Addr]{Op: "btrfstree.ReadNode", NodeAddr: addr, Err: errs}
+ return errs
}
-
- // return
-
- return nodeRef, nil
+ return nil
}
diff --git a/lib/btrfs/io2_lv.go b/lib/btrfs/io2_lv.go
index 856ac20..d05d51f 100644
--- a/lib/btrfs/io2_lv.go
+++ b/lib/btrfs/io2_lv.go
@@ -168,7 +168,7 @@ func (fs *FS) initDev(ctx context.Context, sb btrfstree.Superblock) error {
errs = append(errs, err)
},
btrfstree.TreeWalkHandler{
- Item: func(_ btrfstree.TreePath, item btrfstree.Item) error {
+ Item: func(_ btrfstree.Path, item btrfstree.Item) error {
if item.Key.ItemType != btrfsitem.CHUNK_ITEM_KEY {
return nil
}
diff --git a/lib/btrfs/io3_btree.go b/lib/btrfs/io3_btree.go
index 8d35269..80ab10f 100644
--- a/lib/btrfs/io3_btree.go
+++ b/lib/btrfs/io3_btree.go
@@ -10,8 +10,6 @@ import (
"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"
- "git.lukeshu.com/btrfs-progs-ng/lib/diskio"
)
// This file is ordered from low-level to high-level.
@@ -19,7 +17,7 @@ import (
// btrfstree.NodeSource ////////////////////////////////////////////////////////
// ReadNode implements btrfstree.NodeSource.
-func (fs *FS) ReadNode(path btrfstree.TreePath) (*diskio.Ref[btrfsvol.LogicalAddr, btrfstree.Node], error) {
+func (fs *FS) ReadNode(path btrfstree.Path) (*btrfstree.Node, error) {
return btrfstree.FSReadNode(fs, path)
}
@@ -39,7 +37,7 @@ func (fs *FS) populateTreeUUIDs(ctx context.Context) {
// do nothing
},
btrfstree.TreeWalkHandler{
- Item: func(_ btrfstree.TreePath, item btrfstree.Item) error {
+ Item: func(_ btrfstree.Path, item btrfstree.Item) error {
itemBody, ok := item.Body.(*btrfsitem.Root)
if !ok {
return nil
diff --git a/lib/btrfs/io4_fs.go b/lib/btrfs/io4_fs.go
index b1a1232..0445441 100644
--- a/lib/btrfs/io4_fs.go
+++ b/lib/btrfs/io4_fs.go
@@ -10,7 +10,6 @@ import (
"path/filepath"
"reflect"
"sort"
- "sync"
"github.com/datawire/dlib/derror"
@@ -20,6 +19,7 @@ import (
"git.lukeshu.com/btrfs-progs-ng/lib/btrfs/btrfstree"
"git.lukeshu.com/btrfs-progs-ng/lib/btrfs/btrfsvol"
"git.lukeshu.com/btrfs-progs-ng/lib/containers"
+ "git.lukeshu.com/btrfs-progs-ng/lib/diskio"
"git.lukeshu.com/btrfs-progs-ng/lib/maps"
"git.lukeshu.com/btrfs-progs-ng/lib/slices"
"git.lukeshu.com/btrfs-progs-ng/lib/textui"
@@ -62,15 +62,13 @@ type File struct {
}
type Subvolume struct {
- FS interface {
+ fs interface {
btrfstree.TreeOperator
Superblock() (*btrfstree.Superblock, error)
- ReadAt(p []byte, off btrfsvol.LogicalAddr) (int, error)
+ diskio.ReaderAt[btrfsvol.LogicalAddr]
}
TreeID btrfsprim.ObjID
- NoChecksums bool
-
- initOnce sync.Once
+ noChecksums bool
rootVal btrfsitem.Root
rootErr error
@@ -81,41 +79,57 @@ type Subvolume struct {
fileCache containers.ARCache[btrfsprim.ObjID, *File]
}
-func (sv *Subvolume) init() {
- sv.initOnce.Do(func() {
- root, err := sv.FS.TreeSearch(btrfsprim.ROOT_TREE_OBJECTID, btrfstree.SearchRootItem(sv.TreeID))
- if err != nil {
- sv.rootErr = err
- } else {
- switch rootBody := root.Body.(type) {
- case *btrfsitem.Root:
- sv.rootVal = rootBody.Clone()
- case *btrfsitem.Error:
- sv.rootErr = fmt.Errorf("FS_TREE ROOT_ITEM has malformed body: %w", rootBody.Err)
- default:
- panic(fmt.Errorf("should not happen: ROOT_ITEM has unexpected item type: %T", rootBody))
- }
+func NewSubvolume(
+ fs interface {
+ btrfstree.TreeOperator
+ Superblock() (*btrfstree.Superblock, error)
+ diskio.ReaderAt[btrfsvol.LogicalAddr]
+ },
+ treeID btrfsprim.ObjID,
+ noChecksums bool,
+) *Subvolume {
+ sv := &Subvolume{
+ fs: fs,
+ TreeID: treeID,
+ noChecksums: noChecksums,
+ }
+
+ root, err := sv.fs.TreeSearch(btrfsprim.ROOT_TREE_OBJECTID, btrfstree.SearchRootItem(sv.TreeID))
+ if err != nil {
+ sv.rootErr = err
+ } else {
+ switch rootBody := root.Body.(type) {
+ case *btrfsitem.Root:
+ sv.rootVal = rootBody.Clone()
+ case *btrfsitem.Error:
+ sv.rootErr = fmt.Errorf("FS_TREE ROOT_ITEM has malformed body: %w", rootBody.Err)
+ default:
+ panic(fmt.Errorf("should not happen: ROOT_ITEM has unexpected item type: %T", rootBody))
}
+ }
- sv.bareInodeCache.MaxLen = textui.Tunable(128)
- sv.fullInodeCache.MaxLen = textui.Tunable(128)
- sv.dirCache.MaxLen = textui.Tunable(128)
- sv.fileCache.MaxLen = textui.Tunable(128)
- })
+ sv.bareInodeCache.MaxLen = textui.Tunable(128)
+ sv.fullInodeCache.MaxLen = textui.Tunable(128)
+ sv.dirCache.MaxLen = textui.Tunable(128)
+ sv.fileCache.MaxLen = textui.Tunable(128)
+
+ return sv
+}
+
+func (sv *Subvolume) NewChildSubvolume(childID btrfsprim.ObjID) *Subvolume {
+ return NewSubvolume(sv.fs, childID, sv.noChecksums)
}
func (sv *Subvolume) GetRootInode() (btrfsprim.ObjID, error) {
- sv.init()
return sv.rootVal.RootDirID, sv.rootErr
}
func (sv *Subvolume) LoadBareInode(inode btrfsprim.ObjID) (*BareInode, error) {
- sv.init()
val := containers.LoadOrElse[btrfsprim.ObjID, *BareInode](&sv.bareInodeCache, inode, func(inode btrfsprim.ObjID) (val *BareInode) {
val = &BareInode{
Inode: inode,
}
- item, err := sv.FS.TreeLookup(sv.TreeID, btrfsprim.Key{
+ item, err := sv.fs.TreeLookup(sv.TreeID, btrfsprim.Key{
ObjectID: inode,
ItemType: btrfsitem.INODE_ITEM_KEY,
Offset: 0,
@@ -144,7 +158,6 @@ func (sv *Subvolume) LoadBareInode(inode btrfsprim.ObjID) (*BareInode, error) {
}
func (sv *Subvolume) LoadFullInode(inode btrfsprim.ObjID) (*FullInode, error) {
- sv.init()
val := containers.LoadOrElse[btrfsprim.ObjID, *FullInode](&sv.fullInodeCache, inode, func(indoe btrfsprim.ObjID) (val *FullInode) {
val = &FullInode{
BareInode: BareInode{
@@ -152,7 +165,7 @@ func (sv *Subvolume) LoadFullInode(inode btrfsprim.ObjID) (*FullInode, error) {
},
XAttrs: make(map[string]string),
}
- items, err := sv.FS.TreeSearchAll(sv.TreeID, btrfstree.SearchObject(inode))
+ items, err := sv.fs.TreeSearchAll(sv.TreeID, btrfstree.SearchObject(inode))
if err != nil {
val.Errs = append(val.Errs, err)
if len(items) == 0 {
@@ -199,7 +212,6 @@ func (sv *Subvolume) LoadFullInode(inode btrfsprim.ObjID) (*FullInode, error) {
}
func (sv *Subvolume) LoadDir(inode btrfsprim.ObjID) (*Dir, error) {
- sv.init()
val := containers.LoadOrElse[btrfsprim.ObjID, *Dir](&sv.dirCache, inode, func(inode btrfsprim.ObjID) (val *Dir) {
val = new(Dir)
fullInode, err := sv.LoadFullInode(inode)
@@ -336,7 +348,6 @@ func (dir *Dir) AbsPath() (string, error) {
}
func (sv *Subvolume) LoadFile(inode btrfsprim.ObjID) (*File, error) {
- sv.init()
val := containers.LoadOrElse[btrfsprim.ObjID, *File](&sv.fileCache, inode, func(inode btrfsprim.ObjID) (val *File) {
val = new(File)
fullInode, err := sv.LoadFullInode(inode)
@@ -448,7 +459,7 @@ func (file *File) maybeShortReadAt(dat []byte, off int64) (int, error) {
case btrfsitem.FILE_EXTENT_INLINE:
return copy(dat, extent.BodyInline[offsetWithinExt:offsetWithinExt+readSize]), nil
case btrfsitem.FILE_EXTENT_REG, btrfsitem.FILE_EXTENT_PREALLOC:
- sb, err := file.SV.FS.Superblock()
+ sb, err := file.SV.fs.Superblock()
if err != nil {
return 0, err
}
@@ -457,7 +468,7 @@ func (file *File) maybeShortReadAt(dat []byte, off int64) (int, error) {
Add(btrfsvol.AddrDelta(offsetWithinExt))
var block [btrfssum.BlockSize]byte
blockBeg := (beg / btrfssum.BlockSize) * btrfssum.BlockSize
- n, err := file.SV.FS.ReadAt(block[:], blockBeg)
+ n, err := file.SV.fs.ReadAt(block[:], blockBeg)
if n > int(beg-blockBeg) {
n = copy(dat[:readSize], block[beg-blockBeg:])
} else {
@@ -466,8 +477,8 @@ func (file *File) maybeShortReadAt(dat []byte, off int64) (int, error) {
if err != nil {
return 0, err
}
- if !file.SV.NoChecksums {
- sumRun, err := LookupCSum(file.SV.FS, sb.ChecksumType, blockBeg)
+ if !file.SV.noChecksums {
+ sumRun, err := LookupCSum(file.SV.fs, sb.ChecksumType, blockBeg)
if err != nil {
return 0, fmt.Errorf("checksum@%v: %w", blockBeg, err)
}
diff --git a/lib/btrfsutil/graph.go b/lib/btrfsutil/graph.go
index 09a17b4..35848de 100644
--- a/lib/btrfsutil/graph.go
+++ b/lib/btrfsutil/graph.go
@@ -131,8 +131,8 @@ func (g Graph) insertTreeRoot(sb btrfstree.Superblock, treeID btrfsprim.ObjID) {
})
}
-func NewGraph(sb btrfstree.Superblock) *Graph {
- g := &Graph{
+func NewGraph(sb btrfstree.Superblock) Graph {
+ g := Graph{
Nodes: make(map[btrfsvol.LogicalAddr]GraphNode),
BadNodes: make(map[btrfsvol.LogicalAddr]error),
EdgesFrom: make(map[btrfsvol.LogicalAddr][]*GraphEdge),
@@ -149,29 +149,29 @@ func NewGraph(sb btrfstree.Superblock) *Graph {
return g
}
-func (g Graph) InsertNode(nodeRef *diskio.Ref[btrfsvol.LogicalAddr, btrfstree.Node]) {
+func (g Graph) InsertNode(node *btrfstree.Node) {
nodeData := GraphNode{
- Level: nodeRef.Data.Head.Level,
- Generation: nodeRef.Data.Head.Generation,
- Owner: nodeRef.Data.Head.Owner,
+ Level: node.Head.Level,
+ Generation: node.Head.Generation,
+ Owner: node.Head.Owner,
}
- if nodeRef.Data.Head.Level == 0 {
+ if node.Head.Level == 0 {
cnt := 0
- for _, item := range nodeRef.Data.BodyLeaf {
+ for _, item := range node.BodyLeaf {
if _, ok := item.Body.(*btrfsitem.Root); ok {
cnt++
}
}
kps := make([]GraphEdge, 0, cnt)
- keys := make([]btrfsprim.Key, len(nodeRef.Data.BodyLeaf))
+ keys := make([]btrfsprim.Key, len(node.BodyLeaf))
nodeData.Items = keys
- g.Nodes[nodeRef.Addr] = nodeData
- for i, item := range nodeRef.Data.BodyLeaf {
+ g.Nodes[node.Head.Addr] = nodeData
+ for i, item := range node.BodyLeaf {
keys[i] = item.Key
if itemBody, ok := item.Body.(*btrfsitem.Root); ok {
kps = append(kps, GraphEdge{
- FromRoot: nodeRef.Addr,
+ FromRoot: node.Head.Addr,
FromItem: i,
FromTree: item.Key.ObjectID,
ToNode: itemBody.ByteNr,
@@ -182,15 +182,15 @@ func (g Graph) InsertNode(nodeRef *diskio.Ref[btrfsvol.LogicalAddr, btrfstree.No
}
}
} else {
- g.Nodes[nodeRef.Addr] = nodeData
- kps := make([]GraphEdge, len(nodeRef.Data.BodyInterior))
- for i, kp := range nodeRef.Data.BodyInterior {
+ g.Nodes[node.Head.Addr] = nodeData
+ kps := make([]GraphEdge, len(node.BodyInterior))
+ for i, kp := range node.BodyInterior {
kps[i] = GraphEdge{
- FromNode: nodeRef.Addr,
+ FromNode: node.Head.Addr,
FromItem: i,
- FromTree: nodeRef.Data.Head.Owner,
+ FromTree: node.Head.Owner,
ToNode: kp.BlockPtr,
- ToLevel: nodeRef.Data.Head.Level - 1,
+ ToLevel: node.Head.Level - 1,
ToKey: kp.Key,
ToGeneration: kp.Generation,
}
@@ -209,7 +209,7 @@ func (g Graph) FinalCheck(ctx context.Context, fs diskio.File[btrfsvol.LogicalAd
for laddr := range g.EdgesTo {
if _, ok := g.Nodes[laddr]; !ok {
_, err := btrfstree.ReadNode[btrfsvol.LogicalAddr](fs, sb, laddr, btrfstree.NodeExpectations{
- LAddr: containers.Optional[btrfsvol.LogicalAddr]{OK: true, Val: laddr},
+ LAddr: containers.OptionalValue(laddr),
})
if err == nil {
progressWriter.Done()
diff --git a/lib/btrfsutil/listnodes.go b/lib/btrfsutil/listnodes.go
index 5505d23..70b647c 100644
--- a/lib/btrfsutil/listnodes.go
+++ b/lib/btrfsutil/listnodes.go
@@ -11,7 +11,6 @@ import (
"git.lukeshu.com/btrfs-progs-ng/lib/btrfs/btrfstree"
"git.lukeshu.com/btrfs-progs-ng/lib/btrfs/btrfsvol"
"git.lukeshu.com/btrfs-progs-ng/lib/containers"
- "git.lukeshu.com/btrfs-progs-ng/lib/diskio"
"git.lukeshu.com/btrfs-progs-ng/lib/maps"
"git.lukeshu.com/btrfs-progs-ng/lib/textui"
)
@@ -44,8 +43,8 @@ func (*nodeScanner) ScanSector(context.Context, *btrfs.Device, btrfsvol.Physical
return nil
}
-func (s *nodeScanner) ScanNode(_ context.Context, nodeRef *diskio.Ref[btrfsvol.PhysicalAddr, btrfstree.Node]) error {
- s.nodes.Insert(nodeRef.Data.Head.Addr)
+func (s *nodeScanner) ScanNode(_ context.Context, _ btrfsvol.PhysicalAddr, node *btrfstree.Node) error {
+ s.nodes.Insert(node.Head.Addr)
return nil
}
diff --git a/lib/btrfsutil/old_rebuilt_forrest.go b/lib/btrfsutil/old_rebuilt_forrest.go
index d49f34e..abe3329 100644
--- a/lib/btrfsutil/old_rebuilt_forrest.go
+++ b/lib/btrfsutil/old_rebuilt_forrest.go
@@ -17,7 +17,6 @@ import (
"git.lukeshu.com/btrfs-progs-ng/lib/btrfs/btrfstree"
"git.lukeshu.com/btrfs-progs-ng/lib/btrfs/btrfsvol"
"git.lukeshu.com/btrfs-progs-ng/lib/containers"
- "git.lukeshu.com/btrfs-progs-ng/lib/diskio"
)
type oldRebuiltTree struct {
@@ -27,14 +26,34 @@ type oldRebuiltTree struct {
}
type oldRebuiltTreeError struct {
- Path SkinnyPath
- Err error
+ Min btrfsprim.Key
+ Max btrfsprim.Key
+ Err error
+}
+
+func (e oldRebuiltTreeError) Error() string {
+ return fmt.Sprintf("keys %v-%v: %v", e.Min, e.Max, e.Err)
+}
+
+func (e oldRebuiltTreeError) Unwrap() error {
+ return e.Err
}
type oldRebuiltTreeValue struct {
- Path SkinnyPath
Key btrfsprim.Key
ItemSize uint32
+
+ Node nodeInfo
+ Slot int
+}
+
+type nodeInfo struct {
+ LAddr btrfsvol.LogicalAddr
+ Level uint8
+ Generation btrfsprim.Generation
+ Owner btrfsprim.ObjID
+ MinItem btrfsprim.Key
+ MaxItem btrfsprim.Key
}
// Compare implements containers.Ordered.
@@ -42,15 +61,15 @@ func (a oldRebuiltTreeValue) Compare(b oldRebuiltTreeValue) int {
return a.Key.Compare(b.Key)
}
-func newOldRebuiltTree(arena *SkinnyPathArena) oldRebuiltTree {
+func newOldRebuiltTree() oldRebuiltTree {
return oldRebuiltTree{
Items: new(containers.RBTree[oldRebuiltTreeValue]),
Errors: &containers.IntervalTree[btrfsprim.Key, oldRebuiltTreeError]{
MinFn: func(err oldRebuiltTreeError) btrfsprim.Key {
- return arena.Inflate(err.Path).Node(-1).ToKey
+ return err.Min
},
MaxFn: func(err oldRebuiltTreeError) btrfsprim.Key {
- return arena.Inflate(err.Path).Node(-1).ToMaxKey
+ return err.Max
},
},
}
@@ -60,8 +79,6 @@ type OldRebuiltForrest struct {
ctx context.Context //nolint:containedctx // don't have an option while keeping the same API
inner *btrfs.FS
- arena *SkinnyPathArena
-
// btrfsprim.ROOT_TREE_OBJECTID
rootTreeMu sync.Mutex
rootTree *oldRebuiltTree
@@ -98,19 +115,12 @@ func NewOldRebuiltForrest(ctx context.Context, inner *btrfs.FS) *OldRebuiltForre
}
func (bt *OldRebuiltForrest) RebuiltTree(treeID btrfsprim.ObjID) oldRebuiltTree {
- var treeRoot *btrfstree.TreeRoot
- var sb *btrfstree.Superblock
- var err error
if treeID == btrfsprim.ROOT_TREE_OBJECTID {
bt.rootTreeMu.Lock()
defer bt.rootTreeMu.Unlock()
if bt.rootTree != nil {
return *bt.rootTree
}
- sb, err = bt.inner.Superblock()
- if err == nil {
- treeRoot, err = btrfstree.LookupTreeRoot(bt.inner, *sb, treeID)
- }
} else {
bt.treesMu.Lock()
defer bt.treesMu.Unlock()
@@ -120,29 +130,13 @@ func (bt *OldRebuiltForrest) RebuiltTree(treeID btrfsprim.ObjID) oldRebuiltTree
if cacheEntry, exists := bt.trees[treeID]; exists {
return cacheEntry
}
- sb, err = bt.inner.Superblock()
- if err == nil {
- treeRoot, err = btrfstree.LookupTreeRoot(bt, *sb, treeID)
- }
- }
- if bt.arena == nil {
- var _sb btrfstree.Superblock
- if sb != nil {
- _sb = *sb
- }
- bt.arena = &SkinnyPathArena{
- FS: bt.inner,
- SB: _sb,
- }
- }
- cacheEntry := newOldRebuiltTree(bt.arena)
- if err != nil {
- cacheEntry.RootErr = err
- } else {
- dlog.Infof(bt.ctx, "indexing tree %v...", treeID)
- bt.rawTreeWalk(*treeRoot, cacheEntry, nil)
- dlog.Infof(bt.ctx, "... done indexing tree %v", treeID)
}
+
+ cacheEntry := newOldRebuiltTree()
+ dlog.Infof(bt.ctx, "indexing tree %v...", treeID)
+ bt.rawTreeWalk(treeID, &cacheEntry)
+ dlog.Infof(bt.ctx, "... done indexing tree %v", treeID)
+
if treeID == btrfsprim.ROOT_TREE_OBJECTID {
bt.rootTree = &cacheEntry
} else {
@@ -151,7 +145,20 @@ func (bt *OldRebuiltForrest) RebuiltTree(treeID btrfsprim.ObjID) oldRebuiltTree
return cacheEntry
}
-func (bt *OldRebuiltForrest) rawTreeWalk(root btrfstree.TreeRoot, cacheEntry oldRebuiltTree, walked *[]btrfsprim.Key) {
+func discardOK[T any](x T, _ bool) T { return x }
+
+func (bt *OldRebuiltForrest) rawTreeWalk(treeID btrfsprim.ObjID, cacheEntry *oldRebuiltTree) {
+ sb, err := bt.inner.Superblock()
+ if err != nil {
+ cacheEntry.RootErr = err
+ return
+ }
+ root, err := btrfstree.LookupTreeRoot(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
@@ -159,13 +166,39 @@ func (bt *OldRebuiltForrest) rawTreeWalk(root btrfstree.TreeRoot, cacheEntry old
panic(fmt.Errorf("TODO: error parsing item: %w", err))
}
cacheEntry.Errors.Insert(oldRebuiltTreeError{
- Path: bt.arena.Deflate(err.Path),
- Err: err.Err,
+ Min: err.Path.Node(-1).ToKey,
+ Max: err.Path.Node(-1).ToMaxKey,
+ Err: err.Err,
})
}
+ var curNode nodeInfo
cbs := btrfstree.TreeWalkHandler{
- Item: func(path btrfstree.TreePath, item btrfstree.Item) error {
+ 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
+ },
+ Node: func(path btrfstree.Path, node *btrfstree.Node) error {
+ 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 nil
+ },
+ Item: func(path btrfstree.Path, item btrfstree.Item) error {
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
@@ -173,33 +206,29 @@ func (bt *OldRebuiltForrest) rawTreeWalk(root btrfstree.TreeRoot, cacheEntry old
panic(fmt.Errorf("dup key=%v in tree=%v", item.Key, root.TreeID))
}
cacheEntry.Items.Insert(oldRebuiltTreeValue{
- Path: bt.arena.Deflate(path),
Key: item.Key,
ItemSize: item.BodySize,
+
+ Node: curNode,
+ Slot: path.Node(-1).FromItemSlot,
})
- if walked != nil {
- *walked = append(*walked, item.Key)
- }
return nil
},
}
- btrfstree.TreeOperatorImpl{NodeSource: bt.inner}.RawTreeWalk(bt.ctx, root, errHandle, cbs)
+ 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))
}
-func (bt *OldRebuiltForrest) addErrs(tree oldRebuiltTree, fn func(btrfsprim.Key, uint32) int, err error) error {
+func (tree oldRebuiltTree) addErrs(fn func(btrfsprim.Key, uint32) int, err error) error {
var errs derror.MultiError
tree.Errors.Subrange(
func(k btrfsprim.Key) int { return fn(k, 0) },
func(v oldRebuiltTreeError) bool {
- path := bt.arena.Inflate(v.Path)
- minKey := path.Node(-1).ToKey
- maxKey := path.Node(-1).ToMaxKey
- errs = append(errs, fmt.Errorf("keys %v-%v: %w", minKey, maxKey, v.Err))
+ errs = append(errs, v)
return true
})
if len(errs) == 0 {
@@ -211,6 +240,33 @@ func (bt *OldRebuiltForrest) addErrs(tree oldRebuiltTree, fn func(btrfsprim.Key,
return errs
}
+func (bt *OldRebuiltForrest) readNode(nodeInfo nodeInfo) *btrfstree.Node {
+ sb, err := bt.inner.Superblock()
+ if err != nil {
+ panic(fmt.Errorf("should not happen: i/o error: %w", err))
+ }
+
+ node, err := btrfstree.ReadNode[btrfsvol.LogicalAddr](bt.inner, *sb, nodeInfo.LAddr, btrfstree.NodeExpectations{
+ LAddr: containers.OptionalValue(nodeInfo.LAddr),
+ Level: containers.OptionalValue(nodeInfo.Level),
+ Generation: containers.OptionalValue(nodeInfo.Generation),
+ Owner: func(treeID btrfsprim.ObjID) error {
+ if treeID != nodeInfo.Owner {
+ return fmt.Errorf("expected owner=%v but claims to have owner=%v",
+ nodeInfo.Owner, treeID)
+ }
+ return nil
+ },
+ MinItem: containers.OptionalValue(nodeInfo.MinItem),
+ MaxItem: containers.OptionalValue(nodeInfo.MaxItem),
+ })
+ if err != nil {
+ panic(fmt.Errorf("should not happen: i/o error: %w", err))
+ }
+
+ return node
+}
+
func (bt *OldRebuiltForrest) TreeSearch(treeID btrfsprim.ObjID, searcher btrfstree.TreeSearcher) (btrfstree.Item, error) {
tree := bt.RebuiltTree(treeID)
if tree.RootErr != nil {
@@ -221,21 +277,17 @@ func (bt *OldRebuiltForrest) TreeSearch(treeID btrfsprim.ObjID, searcher btrfstr
return searcher.Search(indexItem.Key, indexItem.ItemSize)
})
if indexItem == nil {
- return btrfstree.Item{}, fmt.Errorf("item with %s: %w", searcher, bt.addErrs(tree, searcher.Search, btrfstree.ErrNoItem))
+ return btrfstree.Item{}, fmt.Errorf("item with %s: %w", searcher, tree.addErrs(searcher.Search, btrfstree.ErrNoItem))
}
- itemPath := bt.arena.Inflate(indexItem.Value.Path)
- node, err := bt.inner.ReadNode(itemPath.Parent())
- defer btrfstree.FreeNodeRef(node)
- if err != nil {
- return btrfstree.Item{}, fmt.Errorf("item with %s: %w", searcher, bt.addErrs(tree, searcher.Search, err))
- }
+ node := bt.readNode(indexItem.Value.Node)
+ defer node.Free()
- item := node.Data.BodyLeaf[itemPath.Node(-1).FromItemSlot]
+ item := node.BodyLeaf[indexItem.Value.Slot]
item.Body = item.Body.CloneItem()
// Since we were only asked to return 1 item, it isn't
- // necessary to augment this `nil` with bt.addErrs().
+ // necessary to augment this `nil` with tree.addErrs().
return item, nil
}
@@ -255,28 +307,22 @@ func (bt *OldRebuiltForrest) TreeSearchAll(treeID btrfsprim.ObjID, searcher btrf
return true
})
if len(indexItems) == 0 {
- return nil, fmt.Errorf("items with %s: %w", searcher, bt.addErrs(tree, searcher.Search, btrfstree.ErrNoItem))
+ return nil, fmt.Errorf("items with %s: %w", searcher, tree.addErrs(searcher.Search, btrfstree.ErrNoItem))
}
ret := make([]btrfstree.Item, len(indexItems))
- var node *diskio.Ref[btrfsvol.LogicalAddr, btrfstree.Node]
- for i := range indexItems {
- itemPath := bt.arena.Inflate(indexItems[i].Path)
- if node == nil || node.Addr != itemPath.Node(-2).ToNodeAddr {
- var err error
- btrfstree.FreeNodeRef(node)
- node, err = bt.inner.ReadNode(itemPath.Parent())
- if err != nil {
- btrfstree.FreeNodeRef(node)
- return nil, fmt.Errorf("items with %s: %w", searcher, bt.addErrs(tree, searcher.Search, err))
- }
+ 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.Data.BodyLeaf[itemPath.Node(-1).FromItemSlot]
+ ret[i] = node.BodyLeaf[indexItem.Slot]
ret[i].Body = ret[i].Body.CloneItem()
}
- btrfstree.FreeNodeRef(node)
+ node.Free()
- err := bt.addErrs(tree, searcher.Search, nil)
+ err := tree.addErrs(searcher.Search, nil)
if err != nil {
err = fmt.Errorf("items with %s: %w", searcher, err)
}
@@ -287,7 +333,7 @@ func (bt *OldRebuiltForrest) TreeWalk(ctx context.Context, treeID btrfsprim.ObjI
tree := bt.RebuiltTree(treeID)
if tree.RootErr != nil {
errHandle(&btrfstree.TreeError{
- Path: btrfstree.TreePath{{
+ Path: btrfstree.Path{{
FromTree: treeID,
ToMaxKey: btrfsprim.MaxKey,
}},
@@ -298,7 +344,7 @@ func (bt *OldRebuiltForrest) TreeWalk(ctx context.Context, treeID btrfsprim.ObjI
if cbs.Item == nil {
return
}
- var node *diskio.Ref[btrfsvol.LogicalAddr, btrfstree.Node]
+ var node *btrfstree.Node
tree.Items.Range(func(indexItem *containers.RBNode[oldRebuiltTreeValue]) bool {
if ctx.Err() != nil {
return false
@@ -306,24 +352,34 @@ func (bt *OldRebuiltForrest) TreeWalk(ctx context.Context, treeID btrfsprim.ObjI
if bt.ctx.Err() != nil {
return false
}
- itemPath := bt.arena.Inflate(indexItem.Value.Path)
- if node == nil || node.Addr != itemPath.Node(-2).ToNodeAddr {
- var err error
- btrfstree.FreeNodeRef(node)
- node, err = bt.inner.ReadNode(itemPath.Parent())
- if err != nil {
- btrfstree.FreeNodeRef(node)
- errHandle(&btrfstree.TreeError{Path: itemPath, Err: err})
- return true
- }
+ if node == nil || node.Head.Addr != indexItem.Value.Node.LAddr {
+ node.Free()
+ node = bt.readNode(indexItem.Value.Node)
+ }
+ item := node.BodyLeaf[indexItem.Value.Slot]
+
+ itemPath := btrfstree.Path{
+ {
+ FromTree: treeID,
+ ToNodeAddr: indexItem.Value.Node.LAddr,
+ ToNodeGeneration: indexItem.Value.Node.Generation,
+ ToNodeLevel: indexItem.Value.Node.Level,
+ ToKey: indexItem.Value.Node.MinItem,
+ ToMaxKey: indexItem.Value.Node.MaxItem,
+ },
+ {
+ FromTree: indexItem.Value.Node.Owner,
+ FromItemSlot: indexItem.Value.Slot,
+ ToKey: indexItem.Value.Key,
+ ToMaxKey: indexItem.Value.Key,
+ },
}
- item := node.Data.BodyLeaf[itemPath.Node(-1).FromItemSlot]
if err := cbs.Item(itemPath, item); err != nil {
errHandle(&btrfstree.TreeError{Path: itemPath, Err: err})
}
return true
})
- btrfstree.FreeNodeRef(node)
+ node.Free()
}
func (bt *OldRebuiltForrest) Superblock() (*btrfstree.Superblock, error) {
@@ -333,27 +389,3 @@ func (bt *OldRebuiltForrest) Superblock() (*btrfstree.Superblock, error) {
func (bt *OldRebuiltForrest) ReadAt(p []byte, off btrfsvol.LogicalAddr) (int, error) {
return bt.inner.ReadAt(p, off)
}
-
-func (bt *OldRebuiltForrest) Augment(treeID btrfsprim.ObjID, nodeAddr btrfsvol.LogicalAddr) ([]btrfsprim.Key, error) {
- sb, err := bt.Superblock()
- if err != nil {
- return nil, err
- }
- tree := bt.RebuiltTree(treeID)
- if tree.RootErr != nil {
- return nil, tree.RootErr
- }
- nodeRef, err := btrfstree.ReadNode[btrfsvol.LogicalAddr](bt.inner, *sb, nodeAddr, btrfstree.NodeExpectations{})
- defer btrfstree.FreeNodeRef(nodeRef)
- if err != nil {
- return nil, err
- }
- var ret []btrfsprim.Key
- bt.rawTreeWalk(btrfstree.TreeRoot{
- TreeID: treeID,
- RootNode: nodeAddr,
- Level: nodeRef.Data.Head.Level,
- Generation: nodeRef.Data.Head.Generation,
- }, tree, &ret)
- return ret, nil
-}
diff --git a/lib/btrfsutil/print_addrspace.go b/lib/btrfsutil/print_addrspace.go
deleted file mode 100644
index ae2c492..0000000
--- a/lib/btrfsutil/print_addrspace.go
+++ /dev/null
@@ -1,73 +0,0 @@
-// Copyright (C) 2022-2023 Luke Shumaker <lukeshu@lukeshu.com>
-//
-// SPDX-License-Identifier: GPL-2.0-or-later
-
-package btrfsutil
-
-import (
- "io"
- "sort"
-
- "git.lukeshu.com/btrfs-progs-ng/lib/btrfs"
- "git.lukeshu.com/btrfs-progs-ng/lib/btrfs/btrfsvol"
- "git.lukeshu.com/btrfs-progs-ng/lib/textui"
-)
-
-func PrintLogicalSpace(out io.Writer, fs *btrfs.FS) {
- mappings := fs.LV.Mappings()
- var prevBeg, prevEnd btrfsvol.LogicalAddr
- var sumHole, sumChunk btrfsvol.AddrDelta
- for _, mapping := range mappings {
- if mapping.LAddr > prevEnd {
- size := mapping.LAddr.Sub(prevEnd)
- textui.Fprintf(out, "logical_hole laddr=%v size=%v\n", prevEnd, size)
- sumHole += size
- }
- if mapping.LAddr != prevBeg {
- if !mapping.Flags.OK {
- textui.Fprintf(out, "chunk laddr=%v size=%v flags=(missing)\n",
- mapping.LAddr, mapping.Size)
- } else {
- textui.Fprintf(out, "chunk laddr=%v size=%v flags=%v\n",
- mapping.LAddr, mapping.Size, mapping.Flags.Val)
- }
- }
- textui.Fprintf(out, "\tstripe dev_id=%v paddr=%v\n",
- mapping.PAddr.Dev, mapping.PAddr.Addr)
- sumChunk += mapping.Size
- prevBeg = mapping.LAddr
- prevEnd = mapping.LAddr.Add(mapping.Size)
- }
- textui.Fprintf(out, "total logical holes = %v (%d)\n", sumHole, int64(sumHole))
- textui.Fprintf(out, "total logical chunks = %v (%d)\n", sumChunk, int64(sumChunk))
- textui.Fprintf(out, "total logical addr space = %v (%d)\n", prevEnd, int64(prevEnd))
-}
-
-func PrintPhysicalSpace(out io.Writer, fs *btrfs.FS) {
- mappings := fs.LV.Mappings()
- sort.Slice(mappings, func(i, j int) bool {
- return mappings[i].PAddr.Compare(mappings[j].PAddr) < 0
- })
-
- var prevDev btrfsvol.DeviceID
- var prevEnd btrfsvol.PhysicalAddr
- var sumHole, sumExt btrfsvol.AddrDelta
- for _, mapping := range mappings {
- if mapping.PAddr.Dev != prevDev {
- prevDev = mapping.PAddr.Dev
- prevEnd = 0
- }
- if mapping.PAddr.Addr > prevEnd {
- size := mapping.PAddr.Addr.Sub(prevEnd)
- textui.Fprintf(out, "physical_hole paddr=%v size=%v\n", prevEnd, size)
- sumHole += size
- }
- textui.Fprintf(out, "devext dev=%v paddr=%v size=%v laddr=%v\n",
- mapping.PAddr.Dev, mapping.PAddr.Addr, mapping.Size, mapping.LAddr)
- sumExt += mapping.Size
- prevEnd = mapping.PAddr.Addr.Add(mapping.Size)
- }
- textui.Fprintf(out, "total physical holes = %v (%d)\n", sumHole, int64(sumHole))
- textui.Fprintf(out, "total physical extents = %v (%d)\n", sumExt, int64(sumExt))
- textui.Fprintf(out, "total physical addr space = %v (%d)\n", prevEnd, int64(prevEnd))
-}
diff --git a/lib/btrfsutil/rebuilt_forrest.go b/lib/btrfsutil/rebuilt_forrest.go
index 70ece13..b5c646d 100644
--- a/lib/btrfsutil/rebuilt_forrest.go
+++ b/lib/btrfsutil/rebuilt_forrest.go
@@ -6,6 +6,8 @@ package btrfsutil
import (
"context"
+ "fmt"
+ "sync"
"github.com/datawire/dlib/dlog"
@@ -14,6 +16,7 @@ import (
"git.lukeshu.com/btrfs-progs-ng/lib/btrfs/btrfstree"
"git.lukeshu.com/btrfs-progs-ng/lib/btrfs/btrfsvol"
"git.lukeshu.com/btrfs-progs-ng/lib/containers"
+ "git.lukeshu.com/btrfs-progs-ng/lib/diskio"
"git.lukeshu.com/btrfs-progs-ng/lib/slices"
"git.lukeshu.com/btrfs-progs-ng/lib/textui"
)
@@ -25,13 +28,71 @@ type RebuiltForrestCallbacks interface {
LookupUUID(ctx context.Context, uuid btrfsprim.UUID) (id btrfsprim.ObjID, ok bool)
}
+type noopRebuiltForrestCallbacks struct {
+ forrest *RebuiltForrest
+}
+
+func (noopRebuiltForrestCallbacks) AddedItem(context.Context, btrfsprim.ObjID, btrfsprim.Key) {}
+func (noopRebuiltForrestCallbacks) AddedRoot(context.Context, btrfsprim.ObjID, btrfsvol.LogicalAddr) {
+}
+
+func (cb noopRebuiltForrestCallbacks) LookupRoot(ctx context.Context, tree btrfsprim.ObjID) (offset btrfsprim.Generation, _item btrfsitem.Root, ok bool) {
+ rootTree := cb.forrest.RebuiltTree(ctx, btrfsprim.ROOT_TREE_OBJECTID)
+ if rootTree == nil {
+ return 0, btrfsitem.Root{}, false
+ }
+ tgt := btrfsprim.Key{
+ ObjectID: tree,
+ ItemType: btrfsprim.ROOT_ITEM_KEY,
+ }
+ itemKey, itemPtr, ok := rootTree.RebuiltItems(ctx).Search(func(key btrfsprim.Key, _ ItemPtr) int {
+ key.Offset = 0
+ return tgt.Compare(key)
+ })
+ itemBody := cb.forrest.readItem(ctx, itemPtr)
+ defer itemBody.Free()
+ switch itemBody := itemBody.(type) {
+ case *btrfsitem.Root:
+ return btrfsprim.Generation(itemKey.Offset), *itemBody, true
+ case *btrfsitem.Error:
+ return 0, btrfsitem.Root{}, false
+ default:
+ // This is a panic because the item decoder should not emit ROOT_ITEM items as anything but
+ // btrfsitem.Root or btrfsitem.Error without this code also being updated.
+ panic(fmt.Errorf("should not happen: ROOT_ITEM item has unexpected type: %T", itemBody))
+ }
+}
+
+func (cb noopRebuiltForrestCallbacks) LookupUUID(ctx context.Context, uuid btrfsprim.UUID) (id btrfsprim.ObjID, ok bool) {
+ uuidTree := cb.forrest.RebuiltTree(ctx, btrfsprim.UUID_TREE_OBJECTID)
+ if uuidTree == nil {
+ return 0, false
+ }
+ tgt := btrfsitem.UUIDToKey(uuid)
+ itemPtr, ok := uuidTree.RebuiltItems(ctx).Load(tgt)
+ if !ok {
+ return 0, false
+ }
+ itemBody := cb.forrest.readItem(ctx, itemPtr)
+ defer itemBody.Free()
+ switch itemBody := itemBody.(type) {
+ case *btrfsitem.UUIDMap:
+ return itemBody.ObjID, true
+ case *btrfsitem.Error:
+ return 0, false
+ default:
+ // This is a panic because the item decoder should not emit UUID_SUBVOL items as anything but
+ // btrfsitem.UUIDMap or btrfsitem.Error without this code also being updated.
+ panic(fmt.Errorf("should not happen: UUID_SUBVOL item has unexpected type: %T", itemBody))
+ }
+}
+
// RebuiltForrest is an abstraction for rebuilding and accessing
// potentially broken btrees.
//
-// It is conceptually a btrfstree.TreeOperator, and adds similar
-// broken-tree handling to OldRebuiltForrest. However, the API is
-// different than btrfstree.TreeOperator, and is much more efficient
-// than OldRebuiltForrest.
+// It is conceptually a btrfstree.Forrest, and adds similar
+// broken-tree handling to OldRebuiltForrest. However, it is much
+// more efficient than OldRebuiltForrest.
//
// The efficiency improvements are possible because of the API
// differences, which are necessary for how it is used in
@@ -40,43 +101,60 @@ type RebuiltForrestCallbacks interface {
// - it consumes an already-read Graph instead of reading the graph
// itself
//
-// - it does not use `btrfstree.TreePath`
+// - it does not use `btrfstree.Path`
//
// - it does not keep track of errors encountered in a tree
//
// Additionally, it provides some functionality that OldRebuiltForrest
// does not:
//
-// - it provides a .LeafToRoots() method to advise on what
-// additional roots should be added
+// - it provides a RebuiltForrest.RebuiltListRoots() method for
+// listing how trees have been repaired.
+//
+// - it provides a RebuiltTree.RebuiltAddRoot() method for repairing a
+// tree.
+//
+// - it provides several RebuiltTree methods that provide advice on
+// what roots should be added to a tree in order to repair it:
+//
+// .RebuiltItems() and RebuiltPotentialItems() to compare what's
+// in the tree and what could be in the tree.
//
-// - it provides a .COWDistance() method to compare how related two
-// trees are
+// .RebuiltLeafToRoots() to map potential items to things that can
+// be passed to .RebuiltAddRoot().
+//
+// .RebuiltCOWDistance() and .RebuiltShouldReplace() to provide
+// information on deciding on an option from
+// .RebuiltLeafToRoots().
//
// A zero RebuiltForrest is invalid; it must be initialized with
// NewRebuiltForrest().
type RebuiltForrest struct {
// static
+ file diskio.File[btrfsvol.LogicalAddr]
sb btrfstree.Superblock
graph Graph
- keyIO *KeyIO
cb RebuiltForrestCallbacks
// mutable
+
treesMu nestedMutex
trees map[btrfsprim.ObjID]*RebuiltTree // must hold .treesMu to access
leafs containers.ARCache[btrfsprim.ObjID, map[btrfsvol.LogicalAddr]containers.Set[btrfsvol.LogicalAddr]]
incItems containers.ARCache[btrfsprim.ObjID, *itemIndex]
excItems containers.ARCache[btrfsprim.ObjID, *itemIndex]
+
+ nodesMu sync.Mutex
+ nodes containers.ARCache[btrfsvol.LogicalAddr, *btrfstree.Node]
}
-// NewRebuiltForrest returns a new RebuiltForrest instance. All of
-// the callbacks must be non-nil.
-func NewRebuiltForrest(sb btrfstree.Superblock, graph Graph, keyIO *KeyIO, cb RebuiltForrestCallbacks) *RebuiltForrest {
- return &RebuiltForrest{
+// NewRebuiltForrest returns a new RebuiltForrest instance. The
+// RebuiltForrestCallbacks may be nil.
+func NewRebuiltForrest(file diskio.File[btrfsvol.LogicalAddr], sb btrfstree.Superblock, graph Graph, cb RebuiltForrestCallbacks) *RebuiltForrest {
+ ret := &RebuiltForrest{
+ file: file,
sb: sb,
graph: graph,
- keyIO: keyIO,
cb: cb,
trees: make(map[btrfsprim.ObjID]*RebuiltTree),
@@ -89,15 +167,31 @@ func NewRebuiltForrest(sb btrfstree.Superblock, graph Graph, keyIO *KeyIO, cb Re
excItems: containers.ARCache[btrfsprim.ObjID, *itemIndex]{
MaxLen: textui.Tunable(8),
},
+
+ nodes: containers.ARCache[btrfsvol.LogicalAddr, *btrfstree.Node]{
+ MaxLen: textui.Tunable(8),
+ OnRemove: func(_ btrfsvol.LogicalAddr, node *btrfstree.Node) {
+ node.Free()
+ },
+ },
}
+ if ret.cb == nil {
+ ret.cb = noopRebuiltForrestCallbacks{
+ forrest: ret,
+ }
+ }
+ return ret
}
-// Tree returns a given tree, initializing it if nescessary. If it is
-// unable to initialize the tree, then nil is returned, and nothing is
-// done to the forrest.
+// RebuiltTree returns a given tree, initializing it if nescessary.
+// If it is unable to initialize the tree, then nil is returned, and
+// nothing is done to the forrest.
//
// The tree is initialized with the normal root node of the tree.
-func (ts *RebuiltForrest) Tree(ctx context.Context, treeID btrfsprim.ObjID) *RebuiltTree {
+//
+// This is identical to .ForrestLookup(), but returns a concrete type
+// rather than an interface.
+func (ts *RebuiltForrest) RebuiltTree(ctx context.Context, treeID btrfsprim.ObjID) *RebuiltTree {
ctx = ts.treesMu.Lock(ctx)
defer ts.treesMu.Unlock()
if !ts.addTree(ctx, treeID, nil) {
@@ -112,8 +206,8 @@ func (ts *RebuiltForrest) addTree(ctx context.Context, treeID btrfsprim.ObjID, s
}
defer func() {
if !ok {
- // Store a negative cache of this. tree.AddRoot() for the ROOT or UUID
- // trees will call .flushNegativeCache().
+ // Store a negative cache of this. tree.RebuiltAddRoot() for the ROOT or
+ // UUID trees will call .flushNegativeCache().
ts.trees[treeID] = nil
}
}()
@@ -172,7 +266,7 @@ func (ts *RebuiltForrest) addTree(ctx context.Context, treeID btrfsprim.ObjID, s
ts.trees[treeID] = tree
if root != 0 {
- tree.AddRoot(ctx, root)
+ tree.RebuiltAddRoot(ctx, root)
}
return true
@@ -188,12 +282,12 @@ func (ts *RebuiltForrest) flushNegativeCache(ctx context.Context) {
}
}
-// ListRoots returns a listing of all initialized trees and their root
-// nodes.
+// RebuiltListRoots returns a listing of all initialized trees and
+// their root nodes.
//
// Do not mutate the set of roots for a tree; it is a pointer to the
// RebuiltForrest's internal set!
-func (ts *RebuiltForrest) ListRoots(ctx context.Context) map[btrfsprim.ObjID]containers.Set[btrfsvol.LogicalAddr] {
+func (ts *RebuiltForrest) RebuiltListRoots(ctx context.Context) map[btrfsprim.ObjID]containers.Set[btrfsvol.LogicalAddr] {
_ = ts.treesMu.Lock(ctx)
defer ts.treesMu.Unlock()
ret := make(map[btrfsprim.ObjID]containers.Set[btrfsvol.LogicalAddr])
diff --git a/lib/btrfsutil/rebuilt_readitem.go b/lib/btrfsutil/rebuilt_readitem.go
index 016299c..ff919f0 100644
--- a/lib/btrfsutil/rebuilt_readitem.go
+++ b/lib/btrfsutil/rebuilt_readitem.go
@@ -7,7 +7,6 @@ package btrfsutil
import (
"context"
"fmt"
- "sync"
"github.com/datawire/dlib/dlog"
@@ -16,8 +15,6 @@ import (
"git.lukeshu.com/btrfs-progs-ng/lib/btrfs/btrfstree"
"git.lukeshu.com/btrfs-progs-ng/lib/btrfs/btrfsvol"
"git.lukeshu.com/btrfs-progs-ng/lib/containers"
- "git.lukeshu.com/btrfs-progs-ng/lib/diskio"
- "git.lukeshu.com/btrfs-progs-ng/lib/textui"
)
type ItemPtr struct {
@@ -29,111 +26,22 @@ func (ptr ItemPtr) String() string {
return fmt.Sprintf("node@%v[%v]", ptr.Node, ptr.Slot)
}
-type SizeAndErr struct {
- Size uint64
- Err error
-}
-
-type FlagsAndErr struct {
- NoDataSum bool
- Err error
-}
-
-type KeyIO struct {
- rawFile diskio.File[btrfsvol.LogicalAddr]
- sb btrfstree.Superblock
- graph Graph
-
- Flags map[ItemPtr]FlagsAndErr // INODE_ITEM
- Names map[ItemPtr][]byte // DIR_INDEX
- Sizes map[ItemPtr]SizeAndErr // EXTENT_CSUM and EXTENT_DATA
-
- mu sync.Mutex
- cache containers.ARCache[btrfsvol.LogicalAddr, *diskio.Ref[btrfsvol.LogicalAddr, btrfstree.Node]]
-}
-
-func NewKeyIO(file diskio.File[btrfsvol.LogicalAddr], sb btrfstree.Superblock) *KeyIO {
- return &KeyIO{
- rawFile: file,
- sb: sb,
-
- Flags: make(map[ItemPtr]FlagsAndErr),
- Names: make(map[ItemPtr][]byte),
- Sizes: make(map[ItemPtr]SizeAndErr),
-
- cache: containers.ARCache[btrfsvol.LogicalAddr, *diskio.Ref[btrfsvol.LogicalAddr, btrfstree.Node]]{
- MaxLen: textui.Tunable(8),
- OnRemove: func(_ btrfsvol.LogicalAddr, nodeRef *diskio.Ref[btrfsvol.LogicalAddr, btrfstree.Node]) {
- btrfstree.FreeNodeRef(nodeRef)
- },
- },
- }
-}
-
-func (o *KeyIO) InsertNode(nodeRef *diskio.Ref[btrfsvol.LogicalAddr, btrfstree.Node]) {
- for i, item := range nodeRef.Data.BodyLeaf {
- ptr := ItemPtr{
- Node: nodeRef.Addr,
- Slot: i,
- }
- switch itemBody := item.Body.(type) {
- case *btrfsitem.Inode:
- o.Flags[ptr] = FlagsAndErr{
- NoDataSum: itemBody.Flags.Has(btrfsitem.INODE_NODATASUM),
- Err: nil,
- }
- case *btrfsitem.DirEntry:
- if item.Key.ItemType == btrfsprim.DIR_INDEX_KEY {
- o.Names[ptr] = append([]byte(nil), itemBody.Name...)
- }
- case *btrfsitem.ExtentCSum:
- o.Sizes[ptr] = SizeAndErr{
- Size: uint64(itemBody.Size()),
- Err: nil,
- }
- case *btrfsitem.FileExtent:
- size, err := itemBody.Size()
- o.Sizes[ptr] = SizeAndErr{
- Size: uint64(size),
- Err: err,
- }
- case *btrfsitem.Error:
- switch item.Key.ItemType {
- case btrfsprim.INODE_ITEM_KEY:
- o.Flags[ptr] = FlagsAndErr{
- Err: fmt.Errorf("error decoding item: ptr=%v (tree=%v key=%v): %w",
- ptr, nodeRef.Data.Head.Owner, item.Key, itemBody.Err),
- }
- case btrfsprim.EXTENT_CSUM_KEY, btrfsprim.EXTENT_DATA_KEY:
- o.Sizes[ptr] = SizeAndErr{
- Err: fmt.Errorf("error decoding item: ptr=%v (tree=%v key=%v): %w",
- ptr, nodeRef.Data.Head.Owner, item.Key, itemBody.Err),
- }
- }
- }
- }
-}
-
-func (o *KeyIO) SetGraph(graph Graph) {
- o.graph = graph
-}
-
-func (o *KeyIO) readNode(ctx context.Context, laddr btrfsvol.LogicalAddr) *diskio.Ref[btrfsvol.LogicalAddr, btrfstree.Node] {
- if cached, ok := o.cache.Load(laddr); ok {
+func (ts *RebuiltForrest) readNode(ctx context.Context, laddr btrfsvol.LogicalAddr) *btrfstree.Node {
+ if cached, ok := ts.nodes.Load(laddr); ok {
dlog.Tracef(ctx, "cache-hit node@%v", laddr)
return cached
}
- graphInfo, ok := o.graph.Nodes[laddr]
+ graphInfo, ok := ts.graph.Nodes[laddr]
if !ok {
panic(fmt.Errorf("should not happen: node@%v is not mentioned in the in-memory graph", laddr))
}
dlog.Debugf(ctx, "cache-miss node@%v, reading...", laddr)
- ref, err := btrfstree.ReadNode(o.rawFile, o.sb, laddr, btrfstree.NodeExpectations{
- LAddr: containers.Optional[btrfsvol.LogicalAddr]{OK: true, Val: laddr},
- Level: containers.Optional[uint8]{OK: true, Val: graphInfo.Level},
- Generation: containers.Optional[btrfsprim.Generation]{OK: true, Val: graphInfo.Generation},
+ node, err := btrfstree.ReadNode[btrfsvol.LogicalAddr](ts.file, ts.sb, laddr, btrfstree.NodeExpectations{
+ LAddr: containers.OptionalValue(laddr),
+ Level: containers.OptionalValue(graphInfo.Level),
+ Generation: containers.OptionalValue(graphInfo.Generation),
Owner: func(treeID btrfsprim.ObjID) error {
if treeID != graphInfo.Owner {
return fmt.Errorf("expected owner=%v but claims to have owner=%v",
@@ -141,30 +49,30 @@ func (o *KeyIO) readNode(ctx context.Context, laddr btrfsvol.LogicalAddr) *diski
}
return nil
},
- MinItem: containers.Optional[btrfsprim.Key]{OK: true, Val: graphInfo.MinItem()},
- MaxItem: containers.Optional[btrfsprim.Key]{OK: true, Val: graphInfo.MaxItem()},
+ MinItem: containers.OptionalValue(graphInfo.MinItem()),
+ MaxItem: containers.OptionalValue(graphInfo.MaxItem()),
})
if err != nil {
panic(fmt.Errorf("should not happen: i/o error: %w", err))
}
- o.cache.Store(laddr, ref)
+ ts.nodes.Store(laddr, node)
- return ref
+ return node
}
-func (o *KeyIO) ReadItem(ctx context.Context, ptr ItemPtr) btrfsitem.Item {
- o.mu.Lock()
- defer o.mu.Unlock()
- if o.graph.Nodes[ptr.Node].Level != 0 {
- panic(fmt.Errorf("should not happen: btrfsutil.KeyIO.ReadItem called for non-leaf node@%v", ptr.Node))
+func (ts *RebuiltForrest) readItem(ctx context.Context, ptr ItemPtr) btrfsitem.Item {
+ ts.nodesMu.Lock()
+ defer ts.nodesMu.Unlock()
+ if ts.graph.Nodes[ptr.Node].Level != 0 {
+ panic(fmt.Errorf("should not happen: btrfsutil.RebuiltForrest.readItem called for non-leaf node@%v", ptr.Node))
}
if ptr.Slot < 0 {
- panic(fmt.Errorf("should not happen: btrfsutil.KeyIO.ReadItem called for negative item slot: %v", ptr.Slot))
+ panic(fmt.Errorf("should not happen: btrfsutil.RebuiltForrest.readItem called for negative item slot: %v", ptr.Slot))
}
- items := o.readNode(ctx, ptr.Node).Data.BodyLeaf
+ items := ts.readNode(ctx, ptr.Node).BodyLeaf
if ptr.Slot >= len(items) {
- panic(fmt.Errorf("should not happen: btrfsutil.KeyIO.ReadItem called for out-of-bounds item slot: slot=%v len=%v",
+ panic(fmt.Errorf("should not happen: btrfsutil.RebuiltForrest.readItem called for out-of-bounds item slot: slot=%v len=%v",
ptr.Slot, len(items)))
}
return items[ptr.Slot].Body.CloneItem()
diff --git a/lib/btrfsutil/rebuilt_tree.go b/lib/btrfsutil/rebuilt_tree.go
index 3133a9e..3fff9b2 100644
--- a/lib/btrfsutil/rebuilt_tree.go
+++ b/lib/btrfsutil/rebuilt_tree.go
@@ -37,9 +37,9 @@ type RebuiltTree struct {
// derived from tree.Roots, which is why it's OK if they get
// evicted.
//
- // 1. tree.leafToRoots() = tree.forrest.leafs.Load(tree.ID)
- // 2. tree.Items() = tree.forrest.incItems.Load(tree.ID)
- // 3. tree.PotentialItems() = tree.forrest.excItems.Load(tree.ID)
+ // 1. tree.leafToRoots() = tree.forrest.leafs.Load(tree.ID)
+ // 2. tree.RebuiltItems() = tree.forrest.incItems.Load(tree.ID)
+ // 3. tree.RebuiltPotentialItems() = tree.forrest.excItems.Load(tree.ID)
}
// evictable member 1: .leafToRoots() //////////////////////////////////////////////////////////////////////////////////
@@ -129,23 +129,23 @@ func (tree *RebuiltTree) isOwnerOK(owner btrfsprim.ObjID, gen btrfsprim.Generati
}
}
-// evictable members 2 and 3: .Items() and .PotentialItems() ///////////////////////////////////////////////////////////
+// evictable members 2 and 3: .RebuiltItems() and .RebuiltPotentialItems() /////////////////////////////////////////////
-// Items returns a map of the items contained in this tree.
+// RebuiltItems returns a map of the items contained in this tree.
//
// Do not mutate the returned map; it is a pointer to the
// RebuiltTree's internal map!
-func (tree *RebuiltTree) Items(ctx context.Context) *containers.SortedMap[btrfsprim.Key, ItemPtr] {
+func (tree *RebuiltTree) RebuiltItems(ctx context.Context) *containers.SortedMap[btrfsprim.Key, ItemPtr] {
ctx = dlog.WithField(ctx, "btrfs.util.rebuilt-tree.index-inc-items", fmt.Sprintf("tree=%v", tree.ID))
return tree.items(ctx, &tree.forrest.incItems, tree.Roots.HasAny)
}
-// PotentialItems returns a map of items that could be added to this
-// tree with .AddRoot().
+// RebuiltPotentialItems returns a map of items that could be added to
+// this tree with .RebuiltAddRoot().
//
// Do not mutate the returned map; it is a pointer to the
// RebuiltTree's internal map!
-func (tree *RebuiltTree) PotentialItems(ctx context.Context) *containers.SortedMap[btrfsprim.Key, ItemPtr] {
+func (tree *RebuiltTree) RebuiltPotentialItems(ctx context.Context) *containers.SortedMap[btrfsprim.Key, ItemPtr] {
ctx = dlog.WithField(ctx, "btrfs.util.rebuilt-tree.index-exc-items", fmt.Sprintf("tree=%v", tree.ID))
return tree.items(ctx, &tree.forrest.excItems,
func(roots containers.Set[btrfsvol.LogicalAddr]) bool {
@@ -198,7 +198,7 @@ func (tree *RebuiltTree) items(ctx context.Context, cache containers.Map[btrfspr
index.Store(itemKey, newPtr)
stats.NumItems++
} else {
- if tree.ShouldReplace(oldPtr.Node, newPtr.Node) {
+ if tree.RebuiltShouldReplace(oldPtr.Node, newPtr.Node) {
index.Store(itemKey, newPtr)
}
stats.NumDups++
@@ -216,9 +216,11 @@ func (tree *RebuiltTree) items(ctx context.Context, cache containers.Map[btrfspr
})
}
-func (tree *RebuiltTree) ShouldReplace(oldNode, newNode btrfsvol.LogicalAddr) bool {
- oldDist, _ := tree.COWDistance(tree.forrest.graph.Nodes[oldNode].Owner)
- newDist, _ := tree.COWDistance(tree.forrest.graph.Nodes[newNode].Owner)
+// main public API /////////////////////////////////////////////////////////////////////////////////////////////////////
+
+func (tree *RebuiltTree) RebuiltShouldReplace(oldNode, newNode btrfsvol.LogicalAddr) bool {
+ oldDist, _ := tree.RebuiltCOWDistance(tree.forrest.graph.Nodes[oldNode].Owner)
+ newDist, _ := tree.RebuiltCOWDistance(tree.forrest.graph.Nodes[newNode].Owner)
switch {
case newDist < oldDist:
// Replace the old one with the new lower-dist one.
@@ -248,8 +250,6 @@ func (tree *RebuiltTree) ShouldReplace(oldNode, newNode btrfsvol.LogicalAddr) bo
}
}
-// .AddRoot() //////////////////////////////////////////////////////////////////////////////////////////////////////////
-
type rootStats struct {
Leafs textui.Portion[int]
AddedLeafs int
@@ -261,10 +261,10 @@ func (s rootStats) String() string {
s.Leafs, s.AddedLeafs, s.AddedItems)
}
-// AddRoot adds an additional root node to the tree. It is useful to
-// call .AddRoot() to re-attach part of the tree that has been broken
-// off.
-func (tree *RebuiltTree) AddRoot(ctx context.Context, rootNode btrfsvol.LogicalAddr) {
+// RebuiltAddRoot adds an additional root node to the tree. It is
+// useful to call .RebuiltAddRoot() to re-attach part of the tree that
+// has been broken off.
+func (tree *RebuiltTree) RebuiltAddRoot(ctx context.Context, rootNode btrfsvol.LogicalAddr) {
tree.mu.Lock()
defer tree.mu.Unlock()
ctx = dlog.WithField(ctx, "btrfs.util.rebuilt-tree.add-root", fmt.Sprintf("tree=%v rootNode=%v", tree.ID, rootNode))
@@ -306,11 +306,9 @@ func (tree *RebuiltTree) AddRoot(ctx context.Context, rootNode btrfsvol.LogicalA
tree.forrest.cb.AddedRoot(ctx, tree.ID, rootNode)
}
-// main public API /////////////////////////////////////////////////////////////////////////////////////////////////////
-
-// COWDistance returns how many COW-snapshots down the 'tree' is from
-// the 'parent'.
-func (tree *RebuiltTree) COWDistance(parentID btrfsprim.ObjID) (dist int, ok bool) {
+// RebuiltCOWDistance returns how many COW-snapshots down the 'tree'
+// is from the 'parent'.
+func (tree *RebuiltTree) RebuiltCOWDistance(parentID btrfsprim.ObjID) (dist int, ok bool) {
for {
if parentID == tree.ID {
return dist, true
@@ -325,18 +323,18 @@ func (tree *RebuiltTree) COWDistance(parentID btrfsprim.ObjID) (dist int, ok boo
// ReadItem reads an item from a tree.
func (tree *RebuiltTree) ReadItem(ctx context.Context, key btrfsprim.Key) btrfsitem.Item {
- ptr, ok := tree.Items(ctx).Load(key)
+ ptr, ok := tree.RebuiltItems(ctx).Load(key)
if !ok {
panic(fmt.Errorf("should not happen: btrfsutil.RebuiltTree.ReadItem called for not-included key: %v", key))
}
- return tree.forrest.keyIO.ReadItem(ctx, ptr)
+ return tree.forrest.readItem(ctx, ptr)
}
-// LeafToRoots returns the list of potential roots (to pass to
-// .AddRoot) that include a given leaf-node.
-func (tree *RebuiltTree) LeafToRoots(ctx context.Context, leaf btrfsvol.LogicalAddr) containers.Set[btrfsvol.LogicalAddr] {
+// RebuiltLeafToRoots returns the list of potential roots (to pass to
+// .RebuiltAddRoot) that include a given leaf-node.
+func (tree *RebuiltTree) RebuiltLeafToRoots(ctx context.Context, leaf btrfsvol.LogicalAddr) containers.Set[btrfsvol.LogicalAddr] {
if tree.forrest.graph.Nodes[leaf].Level != 0 {
- panic(fmt.Errorf("should not happen: (tree=%v).LeafToRoots(leaf=%v): not a leaf",
+ panic(fmt.Errorf("should not happen: (tree=%v).RebuiltLeafToRoots(leaf=%v): not a leaf",
tree.ID, leaf))
}
tree.mu.RLock()
@@ -344,7 +342,7 @@ func (tree *RebuiltTree) LeafToRoots(ctx context.Context, leaf btrfsvol.LogicalA
ret := make(containers.Set[btrfsvol.LogicalAddr])
for root := range tree.leafToRoots(ctx)[leaf] {
if tree.Roots.Has(root) {
- panic(fmt.Errorf("should not happen: (tree=%v).LeafToRoots(leaf=%v): tree contains root=%v but not leaf",
+ panic(fmt.Errorf("should not happen: (tree=%v).RebuiltLeafToRoots(leaf=%v): tree contains root=%v but not leaf",
tree.ID, leaf, root))
}
ret.Insert(root)
diff --git a/lib/btrfsutil/scan.go b/lib/btrfsutil/scan.go
index 97220aa..05b27d5 100644
--- a/lib/btrfsutil/scan.go
+++ b/lib/btrfsutil/scan.go
@@ -19,7 +19,6 @@ import (
"git.lukeshu.com/btrfs-progs-ng/lib/btrfs/btrfssum"
"git.lukeshu.com/btrfs-progs-ng/lib/btrfs/btrfstree"
"git.lukeshu.com/btrfs-progs-ng/lib/btrfs/btrfsvol"
- "git.lukeshu.com/btrfs-progs-ng/lib/diskio"
"git.lukeshu.com/btrfs-progs-ng/lib/textui"
)
@@ -30,7 +29,7 @@ type DeviceScannerFactory[Stats comparable, Result any] func(ctx context.Context
type DeviceScanner[Stats comparable, Result any] interface {
ScanStats() Stats
ScanSector(ctx context.Context, dev *btrfs.Device, paddr btrfsvol.PhysicalAddr) error
- ScanNode(ctx context.Context, nodeRef *diskio.Ref[btrfsvol.PhysicalAddr, btrfstree.Node]) error
+ ScanNode(ctx context.Context, addr btrfsvol.PhysicalAddr, node *btrfstree.Node) error
ScanDone(ctx context.Context) (Result, error)
}
@@ -123,19 +122,19 @@ func ScanOneDevice[Stats comparable, Result any](ctx context.Context, dev *btrfs
}
if checkForNode {
- nodeRef, err := btrfstree.ReadNode[btrfsvol.PhysicalAddr](dev, *sb, pos, btrfstree.NodeExpectations{})
+ node, err := btrfstree.ReadNode[btrfsvol.PhysicalAddr](dev, *sb, pos, btrfstree.NodeExpectations{})
if err != nil {
if !errors.Is(err, btrfstree.ErrNotANode) {
dlog.Errorf(ctx, "error: %v", err)
}
} else {
- if err := scanner.ScanNode(ctx, nodeRef); err != nil {
+ if err := scanner.ScanNode(ctx, pos, node); err != nil {
var zero Result
return zero, err
}
minNextNode = pos + btrfsvol.PhysicalAddr(sb.NodeSize)
}
- btrfstree.FreeNodeRef(nodeRef)
+ node.Free()
}
}
diff --git a/lib/btrfsutil/skinny_paths.go b/lib/btrfsutil/skinny_paths.go
deleted file mode 100644
index adf539b..0000000
--- a/lib/btrfsutil/skinny_paths.go
+++ /dev/null
@@ -1,146 +0,0 @@
-// Copyright (C) 2022-2023 Luke Shumaker <lukeshu@lukeshu.com>
-//
-// SPDX-License-Identifier: GPL-2.0-or-later
-
-package btrfsutil
-
-import (
- "fmt"
-
- "git.lukeshu.com/btrfs-progs-ng/lib/btrfs/btrfstree"
- "git.lukeshu.com/btrfs-progs-ng/lib/btrfs/btrfsvol"
- "git.lukeshu.com/btrfs-progs-ng/lib/containers"
- "git.lukeshu.com/btrfs-progs-ng/lib/diskio"
- "git.lukeshu.com/btrfs-progs-ng/lib/textui"
-)
-
-type skinnyItem struct {
- Node btrfsvol.LogicalAddr
- Item int
-}
-
-type SkinnyPath struct {
- Root btrfsvol.LogicalAddr
- Items []int
-}
-
-type SkinnyPathArena struct {
- FS diskio.File[btrfsvol.LogicalAddr]
- SB btrfstree.Superblock
-
- fatRoots map[btrfsvol.LogicalAddr]btrfstree.TreePathElem
- fatItems containers.ARCache[skinnyItem, btrfstree.TreePathElem]
-}
-
-func (a *SkinnyPathArena) init() {
- if a.fatRoots == nil {
- a.fatRoots = make(map[btrfsvol.LogicalAddr]btrfstree.TreePathElem)
- a.fatItems.MaxLen = textui.Tunable(128 * 1024)
- }
-}
-
-func (a *SkinnyPathArena) getItem(parent btrfstree.TreePath, itemSlot int) (btrfstree.TreePathElem, error) {
- if itemSlot < 0 {
- panic("should not happen")
- }
-
- a.init()
-
- ret, ok := a.fatItems.Load(skinnyItem{
- Node: parent.Node(-1).ToNodeAddr,
- Item: itemSlot,
- })
- if ok {
- return ret, nil
- }
-
- node, err := btrfstree.ReadNode(a.FS, a.SB, parent.Node(-1).ToNodeAddr, btrfstree.NodeExpectations{})
- defer btrfstree.FreeNodeRef(node)
- if err != nil {
- return btrfstree.TreePathElem{}, err
- }
- if node.Data.Head.Level > 0 {
- if itemSlot >= len(node.Data.BodyInterior) {
- panic("should not happen")
- }
- for i, item := range node.Data.BodyInterior {
- toMaxKey := parent.Node(-1).ToMaxKey
- if i+1 < len(node.Data.BodyInterior) {
- toMaxKey = node.Data.BodyInterior[i+1].Key.Mm()
- }
- elem := btrfstree.TreePathElem{
- FromTree: node.Data.Head.Owner,
- FromItemSlot: i,
- ToNodeAddr: item.BlockPtr,
- ToNodeGeneration: item.Generation,
- ToNodeLevel: node.Data.Head.Level - 1,
- ToKey: item.Key,
- ToMaxKey: toMaxKey,
- }
- a.fatItems.Store(skinnyItem{Node: parent.Node(-1).ToNodeAddr, Item: i}, elem)
- if i == itemSlot {
- ret = elem
- }
- }
- } else {
- if itemSlot >= len(node.Data.BodyLeaf) {
- panic("should not happen")
- }
- for i, item := range node.Data.BodyLeaf {
- elem := btrfstree.TreePathElem{
- FromTree: node.Data.Head.Owner,
- FromItemSlot: i,
- ToKey: item.Key,
- ToMaxKey: item.Key,
- }
- a.fatItems.Store(skinnyItem{Node: parent.Node(-1).ToNodeAddr, Item: i}, elem)
- if i == itemSlot {
- ret = elem
- }
- }
- }
-
- return ret, nil
-}
-
-func (a *SkinnyPathArena) Deflate(fat btrfstree.TreePath) SkinnyPath {
- a.init()
-
- var ret SkinnyPath
-
- var prevNode btrfsvol.LogicalAddr
- for i, elem := range fat {
- if i == 0 {
- a.fatRoots[elem.ToNodeAddr] = elem
- ret.Root = elem.ToNodeAddr
- } else {
- a.fatItems.Store(skinnyItem{Node: prevNode, Item: elem.FromItemSlot}, elem)
- ret.Items = append(ret.Items, elem.FromItemSlot)
- }
- prevNode = elem.ToNodeAddr
- }
- return ret
-}
-
-func (a *SkinnyPathArena) Inflate(skinny SkinnyPath) btrfstree.TreePath {
- a.init()
-
- ret := make(btrfstree.TreePath, 0, 1+len(skinny.Items))
-
- root, ok := a.fatRoots[skinny.Root]
- if !ok {
- panic(fmt.Errorf("SkinnyPathArena.Inflate: no stored TreePathElem for root->%v",
- skinny.Root))
- }
- ret = append(ret, root)
-
- for _, itemSlot := range skinny.Items {
- elem, err := a.getItem(ret, itemSlot)
- if err != nil {
- panic(err)
- }
- ret = append(ret, elem)
- }
-
- return ret
-}
diff --git a/lib/btrfsutil/walk.go b/lib/btrfsutil/walk.go
index 355976a..bbdf992 100644
--- a/lib/btrfsutil/walk.go
+++ b/lib/btrfsutil/walk.go
@@ -1,4 +1,4 @@
-// Copyright (C) 2022 Luke Shumaker <lukeshu@lukeshu.com>
+// Copyright (C) 2022-2023 Luke Shumaker <lukeshu@lukeshu.com>
//
// SPDX-License-Identifier: GPL-2.0-or-later
@@ -61,7 +61,7 @@ func WalkAllTrees(ctx context.Context, fs btrfstree.TreeOperator, cbs WalkAllTre
},
}
origItem := cbs.Item
- cbs.Item = func(path btrfstree.TreePath, item btrfstree.Item) error {
+ cbs.Item = func(path btrfstree.Path, item btrfstree.Item) error {
if item.Key.ItemType == btrfsitem.ROOT_ITEM_KEY {
trees = append(trees, struct {
Name string
diff --git a/lib/containers/optional.go b/lib/containers/optional.go
index 5bb7bb6..26ec494 100644
--- a/lib/containers/optional.go
+++ b/lib/containers/optional.go
@@ -13,6 +13,19 @@ type Optional[T any] struct {
Val T
}
+func OptionalValue[T any](val T) Optional[T] {
+ return Optional[T]{
+ OK: true,
+ Val: val,
+ }
+}
+
+func OptionalNil[T any]() Optional[T] {
+ return Optional[T]{
+ OK: false,
+ }
+}
+
var (
_ json.Marshaler = Optional[bool]{}
_ json.Unmarshaler = (*Optional[bool])(nil)
diff --git a/lib/diskio/file_iface.go b/lib/diskio/file_iface.go
index d26ffcc..a30ddb0 100644
--- a/lib/diskio/file_iface.go
+++ b/lib/diskio/file_iface.go
@@ -9,11 +9,15 @@ import (
"io"
)
+type ReaderAt[A ~int64] interface {
+ ReadAt(p []byte, off A) (n int, err error)
+}
+
type File[A ~int64] interface {
Name() string
Size() A
- Close() error
- ReadAt(p []byte, off A) (n int, err error)
+ io.Closer
+ ReaderAt[A]
WriteAt(p []byte, off A) (n int, err error)
}
generated by cgit v1.2.3-2-g168b (git 2.25.1) at 2025-04-09 13:18:37 +0000