From 1bc243ca607c22e232017b0f1b4badcde288a9b3 Mon Sep 17 00:00:00 2001 From: Luke Shumaker Date: Thu, 16 Mar 2023 09:17:35 -0600 Subject: btrfstree: Have ReadNode return a *Node rather than a *diskio.Ref[Addr, Node] ... and take a ReaderAt instead of a diskio.File. --- cmd/btrfs-rec/inspect/dumptrees/print_tree.go | 9 +- cmd/btrfs-rec/inspect/rebuildmappings/scan.go | 25 ++-- cmd/btrfs-rec/inspect/rebuildtrees/scan.go | 10 +- cmd/btrfs-rec/inspect_lstrees.go | 7 +- lib/btrfs/btrfstree/btree.go | 10 +- lib/btrfs/btrfstree/btree_tree.go | 184 +++++++++++++------------- lib/btrfs/btrfstree/readnode.go | 4 +- lib/btrfs/btrfstree/types_node.go | 80 +++++------ lib/btrfs/io3_btree.go | 4 +- lib/btrfs/io4_fs.go | 3 +- lib/btrfsutil/graph.go | 32 ++--- lib/btrfsutil/listnodes.go | 5 +- lib/btrfsutil/old_rebuilt_forrest.go | 37 +++--- lib/btrfsutil/rebuilt_readitem.go | 28 ++-- lib/btrfsutil/scan.go | 9 +- lib/btrfsutil/skinny_paths.go | 24 ++-- lib/diskio/file_iface.go | 8 +- 17 files changed, 228 insertions(+), 251 deletions(-) diff --git a/cmd/btrfs-rec/inspect/dumptrees/print_tree.go b/cmd/btrfs-rec/inspect/dumptrees/print_tree.go index a8c2adf..9572f3a 100644 --- a/cmd/btrfs-rec/inspect/dumptrees/print_tree.go +++ b/cmd/btrfs-rec/inspect/dumptrees/print_tree.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/slices" "git.lukeshu.com/btrfs-progs-ng/lib/textui" ) @@ -100,9 +99,9 @@ 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.TreePath, nodeRef *diskio.Ref[btrfsvol.LogicalAddr, btrfstree.Node]) error { - printHeaderInfo(out, nodeRef.Data) - itemOffset = nodeRef.Data.Size - uint32(nodeHeaderSize) + Node: func(path btrfstree.TreePath, node *btrfstree.Node) error { + printHeaderInfo(out, node) + itemOffset = node.Size - uint32(nodeHeaderSize) return nil }, PreKeyPointer: func(path btrfstree.TreePath, item btrfstree.KeyPointer) error { @@ -375,7 +374,7 @@ func printTree(ctx context.Context, out io.Writer, fs *btrfs.FS, treeID btrfspri } // printHeaderInfo mimics btrfs-progs kernel-shared/print-tree.c:print_header_info() -func printHeaderInfo(out io.Writer, node btrfstree.Node) { +func printHeaderInfo(out io.Writer, node *btrfstree.Node) { var typename string if node.Head.Level > 0 { // interior node typename = "node" diff --git a/cmd/btrfs-rec/inspect/rebuildmappings/scan.go b/cmd/btrfs-rec/inspect/rebuildmappings/scan.go index b88f01c..e23314e 100644 --- a/cmd/btrfs-rec/inspect/rebuildmappings/scan.go +++ b/cmd/btrfs-rec/inspect/rebuildmappings/scan.go @@ -19,7 +19,6 @@ import ( "git.lukeshu.com/btrfs-progs-ng/lib/btrfs/btrfsvol" "git.lukeshu.com/btrfs-progs-ng/lib/btrfsutil" "git.lukeshu.com/btrfs-progs-ng/lib/containers" - "git.lukeshu.com/btrfs-progs-ng/lib/diskio" "git.lukeshu.com/btrfs-progs-ng/lib/textui" ) @@ -121,22 +120,22 @@ func (scanner *deviceScanner) ScanSector(_ context.Context, dev *btrfs.Device, p return nil } -func (scanner *deviceScanner) ScanNode(ctx context.Context, nodeRef *diskio.Ref[btrfsvol.PhysicalAddr, btrfstree.Node]) error { - scanner.result.FoundNodes[nodeRef.Data.Head.Addr] = append(scanner.result.FoundNodes[nodeRef.Data.Head.Addr], nodeRef.Addr) - for i, item := range nodeRef.Data.BodyLeaf { +func (scanner *deviceScanner) ScanNode(ctx context.Context, addr btrfsvol.PhysicalAddr, node *btrfstree.Node) error { + scanner.result.FoundNodes[node.Head.Addr] = append(scanner.result.FoundNodes[node.Head.Addr], addr) + for i, item := range node.BodyLeaf { switch item.Key.ItemType { case btrfsitem.CHUNK_ITEM_KEY: switch itemBody := item.Body.(type) { case *btrfsitem.Chunk: dlog.Tracef(ctx, "node@%v: item %v: found chunk", - nodeRef.Addr, i) + addr, i) scanner.result.FoundChunks = append(scanner.result.FoundChunks, btrfstree.SysChunk{ Key: item.Key, Chunk: *itemBody, }) case *btrfsitem.Error: dlog.Errorf(ctx, "node@%v: item %v: error: malformed CHUNK_ITEM: %v", - nodeRef.Addr, i, itemBody.Err) + addr, i, itemBody.Err) default: panic(fmt.Errorf("should not happen: CHUNK_ITEM has unexpected item type: %T", itemBody)) } @@ -144,14 +143,14 @@ func (scanner *deviceScanner) ScanNode(ctx context.Context, nodeRef *diskio.Ref[ switch itemBody := item.Body.(type) { case *btrfsitem.BlockGroup: dlog.Tracef(ctx, "node@%v: item %v: found block group", - nodeRef.Addr, i) + addr, i) scanner.result.FoundBlockGroups = append(scanner.result.FoundBlockGroups, SysBlockGroup{ Key: item.Key, BG: *itemBody, }) case *btrfsitem.Error: dlog.Errorf(ctx, "node@%v: item %v: error: malformed BLOCK_GROUP_ITEM: %v", - nodeRef.Addr, i, itemBody.Err) + addr, i, itemBody.Err) default: panic(fmt.Errorf("should not happen: BLOCK_GROUP_ITEM has unexpected item type: %T", itemBody)) } @@ -159,14 +158,14 @@ func (scanner *deviceScanner) ScanNode(ctx context.Context, nodeRef *diskio.Ref[ switch itemBody := item.Body.(type) { case *btrfsitem.DevExtent: dlog.Tracef(ctx, "node@%v: item %v: found dev extent", - nodeRef.Addr, i) + addr, i) scanner.result.FoundDevExtents = append(scanner.result.FoundDevExtents, SysDevExtent{ Key: item.Key, DevExt: *itemBody, }) case *btrfsitem.Error: dlog.Errorf(ctx, "node@%v: item %v: error: malformed DEV_EXTENT: %v", - nodeRef.Addr, i, itemBody.Err) + addr, i, itemBody.Err) default: panic(fmt.Errorf("should not happen: DEV_EXTENT has unexpected item type: %T", itemBody)) } @@ -174,14 +173,14 @@ func (scanner *deviceScanner) ScanNode(ctx context.Context, nodeRef *diskio.Ref[ switch itemBody := item.Body.(type) { case *btrfsitem.ExtentCSum: dlog.Tracef(ctx, "node@%v: item %v: found csums", - nodeRef.Addr, i) + addr, i) scanner.result.FoundExtentCSums = append(scanner.result.FoundExtentCSums, SysExtentCSum{ - Generation: nodeRef.Data.Head.Generation, + Generation: node.Head.Generation, Sums: *itemBody, }) case *btrfsitem.Error: dlog.Errorf(ctx, "node@%v: item %v: error: malformed is EXTENT_CSUM: %v", - nodeRef.Addr, i, itemBody.Err) + addr, i, itemBody.Err) default: panic(fmt.Errorf("should not happen: EXTENT_CSUM has unexpected item type: %T", itemBody)) } diff --git a/cmd/btrfs-rec/inspect/rebuildtrees/scan.go b/cmd/btrfs-rec/inspect/rebuildtrees/scan.go index ba56c5b..4bc09ad 100644 --- a/cmd/btrfs-rec/inspect/rebuildtrees/scan.go +++ b/cmd/btrfs-rec/inspect/rebuildtrees/scan.go @@ -41,18 +41,18 @@ func ScanDevices(ctx context.Context, fs *btrfs.FS, nodeList []btrfsvol.LogicalA if err := ctx.Err(); err != nil { return btrfstree.Superblock{}, btrfsutil.Graph{}, nil, err } - nodeRef, err := btrfstree.ReadNode[btrfsvol.LogicalAddr](fs, *sb, laddr, btrfstree.NodeExpectations{ + node, err := btrfstree.ReadNode[btrfsvol.LogicalAddr](fs, *sb, laddr, btrfstree.NodeExpectations{ LAddr: containers.Optional[btrfsvol.LogicalAddr]{OK: true, Val: laddr}, }) if err != nil { - btrfstree.FreeNodeRef(nodeRef) + node.Free() return btrfstree.Superblock{}, btrfsutil.Graph{}, nil, err } - nodeGraph.InsertNode(nodeRef) - keyIO.InsertNode(nodeRef) + nodeGraph.InsertNode(node) + keyIO.InsertNode(node) - btrfstree.FreeNodeRef(nodeRef) + node.Free() stats.N++ progressWriter.Set(stats) diff --git a/cmd/btrfs-rec/inspect_lstrees.go b/cmd/btrfs-rec/inspect_lstrees.go index 05c3a57..70f4f51 100644 --- a/cmd/btrfs-rec/inspect_lstrees.go +++ b/cmd/btrfs-rec/inspect_lstrees.go @@ -19,7 +19,6 @@ import ( "git.lukeshu.com/btrfs-progs-ng/lib/btrfs/btrfsvol" "git.lukeshu.com/btrfs-progs-ng/lib/btrfsutil" "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" @@ -76,8 +75,8 @@ func init() { treeErrCnt++ }, TreeWalkHandler: btrfstree.TreeWalkHandler{ - Node: func(_ btrfstree.TreePath, ref *diskio.Ref[btrfsvol.LogicalAddr, btrfstree.Node]) error { - visitedNodes.Insert(ref.Addr) + Node: func(path btrfstree.TreePath, node *btrfstree.Node) error { + visitedNodes.Insert(path.Node(-1).ToNodeAddr) return nil }, Item: func(_ btrfstree.TreePath, item btrfstree.Item) error { @@ -113,7 +112,7 @@ func init() { treeErrCnt++ continue } - for _, item := range node.Data.BodyLeaf { + for _, item := range node.BodyLeaf { typ := item.Key.ItemType treeItemCnt[typ]++ } diff --git a/lib/btrfs/btrfstree/btree.go b/lib/btrfs/btrfstree/btree.go index 89d4f9d..c71aad5 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 { @@ -72,9 +70,9 @@ type TreeWalkHandler struct { // 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 + Node func(TreePath, *Node) error + BadNode func(TreePath, *Node, error) error + PostNode func(TreePath, *Node) error // Callbacks for items on interior nodes PreKeyPointer func(TreePath, KeyPointer) error PostKeyPointer func(TreePath, KeyPointer) 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(TreePath) (*Node, error) } diff --git a/lib/btrfs/btrfstree/btree_tree.go b/lib/btrfs/btrfstree/btree_tree.go index 1e3c789..7561314 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" ) @@ -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, + 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 { + for i, item := range node.BodyLeaf { itemPath := append(path, TreePathElem{ - FromTree: node.Data.Head.Owner, + FromTree: node.Head.Owner, FromItemSlot: i, ToKey: item.Key, ToMaxKey: item.Key, @@ -169,7 +167,7 @@ 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) { +func (fs TreeOperatorImpl) treeSearch(treeRoot TreeRoot, fn func(btrfsprim.Key, uint32) int) (TreePath, *Node, error) { path := TreePath{{ FromTree: treeRoot.TreeID, FromItemSlot: -1, @@ -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, + 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, + 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 TreePath, node *Node) (TreePath, *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 { + if node.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, + 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, + 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 TreePath, node *Node) (TreePath, *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, + 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, + 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/readnode.go b/lib/btrfs/btrfstree/readnode.go index 4ccc17b..1c242ac 100644 --- a/lib/btrfs/btrfstree/readnode.go +++ b/lib/btrfs/btrfstree/readnode.go @@ -1,4 +1,4 @@ -// Copyright (C) 2022 Luke Shumaker +// Copyright (C) 2022-2023 Luke Shumaker // // SPDX-License-Identifier: GPL-2.0-or-later @@ -34,7 +34,7 @@ type NodeFile interface { func FSReadNode( fs NodeFile, path TreePath, -) (*diskio.Ref[btrfsvol.LogicalAddr, Node], error) { +) (*Node, error) { sb, err := fs.Superblock() if err != nil { return nil, fmt.Errorf("btrfs.FS.ReadNode: %w", err) diff --git a/lib/btrfs/btrfstree/types_node.go b/lib/btrfs/btrfstree/types_node.go index 8295ccb..2147f5b 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,9 +514,9 @@ 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) @@ -540,40 +524,40 @@ func ReadNode[Addr ~int64](fs diskio.File[Addr], sb Superblock, addr Addr, exp N // sanity checking (that doesn't prevent parsing) 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 node, &NodeError[Addr]{Op: "btrfstree.ReadNode", NodeAddr: addr, Err: errs} } // return - return nodeRef, nil + return node, nil } diff --git a/lib/btrfs/io3_btree.go b/lib/btrfs/io3_btree.go index 8d35269..467bbde 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.TreePath) (*btrfstree.Node, error) { return btrfstree.FSReadNode(fs, path) } diff --git a/lib/btrfs/io4_fs.go b/lib/btrfs/io4_fs.go index b1a1232..e4511a5 100644 --- a/lib/btrfs/io4_fs.go +++ b/lib/btrfs/io4_fs.go @@ -20,6 +20,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" @@ -65,7 +66,7 @@ type Subvolume struct { 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 diff --git a/lib/btrfsutil/graph.go b/lib/btrfsutil/graph.go index 09a17b4..a7c299a 100644 --- a/lib/btrfsutil/graph.go +++ b/lib/btrfsutil/graph.go @@ -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, } 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..2ec1d83 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 { @@ -226,12 +225,12 @@ func (bt *OldRebuiltForrest) TreeSearch(treeID btrfsprim.ObjID, searcher btrfstr itemPath := bt.arena.Inflate(indexItem.Value.Path) node, err := bt.inner.ReadNode(itemPath.Parent()) - defer btrfstree.FreeNodeRef(node) + defer node.Free() if err != nil { return btrfstree.Item{}, fmt.Errorf("item with %s: %w", searcher, bt.addErrs(tree, searcher.Search, err)) } - item := node.Data.BodyLeaf[itemPath.Node(-1).FromItemSlot] + item := node.BodyLeaf[itemPath.Node(-1).FromItemSlot] item.Body = item.Body.CloneItem() // Since we were only asked to return 1 item, it isn't @@ -259,22 +258,22 @@ func (bt *OldRebuiltForrest) TreeSearchAll(treeID btrfsprim.ObjID, searcher btrf } ret := make([]btrfstree.Item, len(indexItems)) - var node *diskio.Ref[btrfsvol.LogicalAddr, btrfstree.Node] + var node *btrfstree.Node for i := range indexItems { itemPath := bt.arena.Inflate(indexItems[i].Path) - if node == nil || node.Addr != itemPath.Node(-2).ToNodeAddr { + if node == nil || node.Head.Addr != itemPath.Node(-2).ToNodeAddr { var err error - btrfstree.FreeNodeRef(node) + node.Free() node, err = bt.inner.ReadNode(itemPath.Parent()) if err != nil { - btrfstree.FreeNodeRef(node) + node.Free() return nil, fmt.Errorf("items with %s: %w", searcher, bt.addErrs(tree, searcher.Search, err)) } } - ret[i] = node.Data.BodyLeaf[itemPath.Node(-1).FromItemSlot] + ret[i] = node.BodyLeaf[itemPath.Node(-1).FromItemSlot] ret[i].Body = ret[i].Body.CloneItem() } - btrfstree.FreeNodeRef(node) + node.Free() err := bt.addErrs(tree, searcher.Search, nil) if err != nil { @@ -298,7 +297,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 @@ -307,23 +306,23 @@ func (bt *OldRebuiltForrest) TreeWalk(ctx context.Context, treeID btrfsprim.ObjI return false } itemPath := bt.arena.Inflate(indexItem.Value.Path) - if node == nil || node.Addr != itemPath.Node(-2).ToNodeAddr { + if node == nil || node.Head.Addr != itemPath.Node(-2).ToNodeAddr { var err error - btrfstree.FreeNodeRef(node) + node.Free() node, err = bt.inner.ReadNode(itemPath.Parent()) if err != nil { - btrfstree.FreeNodeRef(node) + node.Free() errHandle(&btrfstree.TreeError{Path: itemPath, Err: err}) return true } } - item := node.Data.BodyLeaf[itemPath.Node(-1).FromItemSlot] + item := node.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) { @@ -343,8 +342,8 @@ func (bt *OldRebuiltForrest) Augment(treeID btrfsprim.ObjID, nodeAddr btrfsvol.L if tree.RootErr != nil { return nil, tree.RootErr } - nodeRef, err := btrfstree.ReadNode[btrfsvol.LogicalAddr](bt.inner, *sb, nodeAddr, btrfstree.NodeExpectations{}) - defer btrfstree.FreeNodeRef(nodeRef) + node, err := btrfstree.ReadNode[btrfsvol.LogicalAddr](bt.inner, *sb, nodeAddr, btrfstree.NodeExpectations{}) + defer node.Free() if err != nil { return nil, err } @@ -352,8 +351,8 @@ func (bt *OldRebuiltForrest) Augment(treeID btrfsprim.ObjID, nodeAddr btrfsvol.L bt.rawTreeWalk(btrfstree.TreeRoot{ TreeID: treeID, RootNode: nodeAddr, - Level: nodeRef.Data.Head.Level, - Generation: nodeRef.Data.Head.Generation, + Level: node.Head.Level, + Generation: node.Head.Generation, }, tree, &ret) return ret, nil } diff --git a/lib/btrfsutil/rebuilt_readitem.go b/lib/btrfsutil/rebuilt_readitem.go index 016299c..b1a0656 100644 --- a/lib/btrfsutil/rebuilt_readitem.go +++ b/lib/btrfsutil/rebuilt_readitem.go @@ -49,7 +49,7 @@ type KeyIO struct { Sizes map[ItemPtr]SizeAndErr // EXTENT_CSUM and EXTENT_DATA mu sync.Mutex - cache containers.ARCache[btrfsvol.LogicalAddr, *diskio.Ref[btrfsvol.LogicalAddr, btrfstree.Node]] + cache containers.ARCache[btrfsvol.LogicalAddr, *btrfstree.Node] } func NewKeyIO(file diskio.File[btrfsvol.LogicalAddr], sb btrfstree.Superblock) *KeyIO { @@ -61,19 +61,19 @@ func NewKeyIO(file diskio.File[btrfsvol.LogicalAddr], sb btrfstree.Superblock) * Names: make(map[ItemPtr][]byte), Sizes: make(map[ItemPtr]SizeAndErr), - cache: containers.ARCache[btrfsvol.LogicalAddr, *diskio.Ref[btrfsvol.LogicalAddr, btrfstree.Node]]{ + cache: containers.ARCache[btrfsvol.LogicalAddr, *btrfstree.Node]{ MaxLen: textui.Tunable(8), - OnRemove: func(_ btrfsvol.LogicalAddr, nodeRef *diskio.Ref[btrfsvol.LogicalAddr, btrfstree.Node]) { - btrfstree.FreeNodeRef(nodeRef) + OnRemove: func(_ btrfsvol.LogicalAddr, node *btrfstree.Node) { + node.Free() }, }, } } -func (o *KeyIO) InsertNode(nodeRef *diskio.Ref[btrfsvol.LogicalAddr, btrfstree.Node]) { - for i, item := range nodeRef.Data.BodyLeaf { +func (o *KeyIO) InsertNode(node *btrfstree.Node) { + for i, item := range node.BodyLeaf { ptr := ItemPtr{ - Node: nodeRef.Addr, + Node: node.Head.Addr, Slot: i, } switch itemBody := item.Body.(type) { @@ -102,12 +102,12 @@ func (o *KeyIO) InsertNode(nodeRef *diskio.Ref[btrfsvol.LogicalAddr, btrfstree.N 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), + ptr, node.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), + ptr, node.Head.Owner, item.Key, itemBody.Err), } } } @@ -118,7 +118,7 @@ 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] { +func (o *KeyIO) readNode(ctx context.Context, laddr btrfsvol.LogicalAddr) *btrfstree.Node { if cached, ok := o.cache.Load(laddr); ok { dlog.Tracef(ctx, "cache-hit node@%v", laddr) return cached @@ -130,7 +130,7 @@ func (o *KeyIO) readNode(ctx context.Context, laddr btrfsvol.LogicalAddr) *diski } dlog.Debugf(ctx, "cache-miss node@%v, reading...", laddr) - ref, err := btrfstree.ReadNode(o.rawFile, o.sb, laddr, btrfstree.NodeExpectations{ + node, err := btrfstree.ReadNode[btrfsvol.LogicalAddr](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}, @@ -148,9 +148,9 @@ func (o *KeyIO) readNode(ctx context.Context, laddr btrfsvol.LogicalAddr) *diski panic(fmt.Errorf("should not happen: i/o error: %w", err)) } - o.cache.Store(laddr, ref) + o.cache.Store(laddr, node) - return ref + return node } func (o *KeyIO) ReadItem(ctx context.Context, ptr ItemPtr) btrfsitem.Item { @@ -162,7 +162,7 @@ func (o *KeyIO) ReadItem(ctx context.Context, ptr ItemPtr) btrfsitem.Item { if ptr.Slot < 0 { panic(fmt.Errorf("should not happen: btrfsutil.KeyIO.ReadItem called for negative item slot: %v", ptr.Slot)) } - items := o.readNode(ctx, ptr.Node).Data.BodyLeaf + items := o.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", ptr.Slot, len(items))) 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 index adf539b..1361fff 100644 --- a/lib/btrfsutil/skinny_paths.go +++ b/lib/btrfsutil/skinny_paths.go @@ -54,26 +54,26 @@ func (a *SkinnyPathArena) getItem(parent btrfstree.TreePath, itemSlot int) (btrf return ret, nil } - node, err := btrfstree.ReadNode(a.FS, a.SB, parent.Node(-1).ToNodeAddr, btrfstree.NodeExpectations{}) - defer btrfstree.FreeNodeRef(node) + node, err := btrfstree.ReadNode[btrfsvol.LogicalAddr](a.FS, a.SB, parent.Node(-1).ToNodeAddr, btrfstree.NodeExpectations{}) + defer node.Free() if err != nil { return btrfstree.TreePathElem{}, err } - if node.Data.Head.Level > 0 { - if itemSlot >= len(node.Data.BodyInterior) { + if node.Head.Level > 0 { + if itemSlot >= len(node.BodyInterior) { panic("should not happen") } - for i, item := range node.Data.BodyInterior { + for i, item := range node.BodyInterior { toMaxKey := parent.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() } elem := btrfstree.TreePathElem{ - FromTree: node.Data.Head.Owner, + 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, } @@ -83,12 +83,12 @@ func (a *SkinnyPathArena) getItem(parent btrfstree.TreePath, itemSlot int) (btrf } } } else { - if itemSlot >= len(node.Data.BodyLeaf) { + if itemSlot >= len(node.BodyLeaf) { panic("should not happen") } - for i, item := range node.Data.BodyLeaf { + for i, item := range node.BodyLeaf { elem := btrfstree.TreePathElem{ - FromTree: node.Data.Head.Owner, + FromTree: node.Head.Owner, FromItemSlot: i, ToKey: item.Key, ToMaxKey: item.Key, 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) } -- cgit v1.1-4-g5e80 From 3d5689be1f38ce4d76af5c1a9b6ad1193e6bff67 Mon Sep 17 00:00:00 2001 From: Luke Shumaker Date: Thu, 16 Mar 2023 09:21:41 -0600 Subject: btrfstree: Factor out NodeExpectations.Check() from ReadNode() --- lib/btrfs/btrfstree/types_node.go | 17 ++++++++++++----- 1 file changed, 12 insertions(+), 5 deletions(-) diff --git a/lib/btrfs/btrfstree/types_node.go b/lib/btrfs/btrfstree/types_node.go index 2147f5b..622f23c 100644 --- a/lib/btrfs/btrfstree/types_node.go +++ b/lib/btrfs/btrfstree/types_node.go @@ -523,6 +523,16 @@ func ReadNode[Addr ~int64](fs diskio.ReaderAt[Addr], sb Superblock, addr Addr, e // 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 && node.Head.Addr != exp.LAddr.Val { errs = append(errs, fmt.Errorf("read from laddr=%v but claims to be at laddr=%v", @@ -554,10 +564,7 @@ func ReadNode[Addr ~int64](fs diskio.ReaderAt[Addr], sb Superblock, addr Addr, e } } if len(errs) > 0 { - return node, &NodeError[Addr]{Op: "btrfstree.ReadNode", NodeAddr: addr, Err: errs} + return errs } - - // return - - return node, nil + return nil } -- cgit v1.1-4-g5e80 From 8b5aa5b60839b39f75257ee1c2bafa59459a80e6 Mon Sep 17 00:00:00 2001 From: Luke Shumaker Date: Fri, 17 Mar 2023 22:20:10 -0400 Subject: btrfsutil: OldRebuiltForrest: Don't use Paths when tracking errors --- lib/btrfsutil/old_rebuilt_forrest.go | 33 ++++++++++++++++++++------------- 1 file changed, 20 insertions(+), 13 deletions(-) diff --git a/lib/btrfsutil/old_rebuilt_forrest.go b/lib/btrfsutil/old_rebuilt_forrest.go index 2ec1d83..a6c2661 100644 --- a/lib/btrfsutil/old_rebuilt_forrest.go +++ b/lib/btrfsutil/old_rebuilt_forrest.go @@ -26,8 +26,17 @@ 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 { @@ -41,15 +50,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 }, }, } @@ -134,7 +143,7 @@ func (bt *OldRebuiltForrest) RebuiltTree(treeID btrfsprim.ObjID) oldRebuiltTree SB: _sb, } } - cacheEntry := newOldRebuiltTree(bt.arena) + cacheEntry := newOldRebuiltTree() if err != nil { cacheEntry.RootErr = err } else { @@ -158,8 +167,9 @@ 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, }) } @@ -190,15 +200,12 @@ func (bt *OldRebuiltForrest) TreeLookup(treeID btrfsprim.ObjID, key btrfsprim.Ke return bt.TreeSearch(treeID, btrfstree.SearchExactKey(key)) } -func (bt *OldRebuiltForrest) addErrs(tree oldRebuiltTree, fn func(btrfsprim.Key, uint32) int, err error) error { +func (*OldRebuiltForrest) addErrs(tree oldRebuiltTree, 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 { -- cgit v1.1-4-g5e80 From 95e542df75675389a3598150be9c85c4834bbb98 Mon Sep 17 00:00:00 2001 From: Luke Shumaker Date: Fri, 17 Mar 2023 22:26:42 -0400 Subject: btrfsutil: OldRebuiltForrest: Move .addErrs() from the forrest to the tree --- lib/btrfsutil/old_rebuilt_forrest.go | 14 +++++++------- 1 file changed, 7 insertions(+), 7 deletions(-) diff --git a/lib/btrfsutil/old_rebuilt_forrest.go b/lib/btrfsutil/old_rebuilt_forrest.go index a6c2661..6705535 100644 --- a/lib/btrfsutil/old_rebuilt_forrest.go +++ b/lib/btrfsutil/old_rebuilt_forrest.go @@ -200,7 +200,7 @@ func (bt *OldRebuiltForrest) TreeLookup(treeID btrfsprim.ObjID, key btrfsprim.Ke return bt.TreeSearch(treeID, btrfstree.SearchExactKey(key)) } -func (*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) }, @@ -227,21 +227,21 @@ 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 node.Free() if err != nil { - return btrfstree.Item{}, fmt.Errorf("item with %s: %w", searcher, bt.addErrs(tree, searcher.Search, err)) + return btrfstree.Item{}, fmt.Errorf("item with %s: %w", searcher, tree.addErrs(searcher.Search, err)) } item := node.BodyLeaf[itemPath.Node(-1).FromItemSlot] 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 } @@ -261,7 +261,7 @@ 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)) @@ -274,7 +274,7 @@ func (bt *OldRebuiltForrest) TreeSearchAll(treeID btrfsprim.ObjID, searcher btrf node, err = bt.inner.ReadNode(itemPath.Parent()) if err != nil { node.Free() - return nil, fmt.Errorf("items with %s: %w", searcher, bt.addErrs(tree, searcher.Search, err)) + return nil, fmt.Errorf("items with %s: %w", searcher, tree.addErrs(searcher.Search, err)) } } ret[i] = node.BodyLeaf[itemPath.Node(-1).FromItemSlot] @@ -282,7 +282,7 @@ func (bt *OldRebuiltForrest) TreeSearchAll(treeID btrfsprim.ObjID, searcher btrf } 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) } -- cgit v1.1-4-g5e80 From b97b6962d5027ae3db2bb03db1e5303702c3e9b2 Mon Sep 17 00:00:00 2001 From: Luke Shumaker Date: Thu, 2 Mar 2023 16:02:42 -0700 Subject: btrfsutil: OldRebuiltForrest: Drop skinny paths This changes errors to not have a Path attached to them, only tracking their spans; and it changes the Paths from TreeWalk to only have the leaf node. --- lib/btrfsutil/old_rebuilt_forrest.go | 137 ++++++++++++++++++++++---------- lib/btrfsutil/skinny_paths.go | 146 ----------------------------------- 2 files changed, 97 insertions(+), 186 deletions(-) delete mode 100644 lib/btrfsutil/skinny_paths.go diff --git a/lib/btrfsutil/old_rebuilt_forrest.go b/lib/btrfsutil/old_rebuilt_forrest.go index 6705535..8bc02df 100644 --- a/lib/btrfsutil/old_rebuilt_forrest.go +++ b/lib/btrfsutil/old_rebuilt_forrest.go @@ -40,9 +40,20 @@ func (e oldRebuiltTreeError) Unwrap() error { } 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. @@ -68,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 @@ -133,16 +142,7 @@ func (bt *OldRebuiltForrest) RebuiltTree(treeID btrfsprim.ObjID) oldRebuiltTree 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() if err != nil { cacheEntry.RootErr = err @@ -151,6 +151,7 @@ func (bt *OldRebuiltForrest) RebuiltTree(treeID btrfsprim.ObjID) oldRebuiltTree bt.rawTreeWalk(*treeRoot, cacheEntry, nil) dlog.Infof(bt.ctx, "... done indexing tree %v", treeID) } + if treeID == btrfsprim.ROOT_TREE_OBJECTID { bt.rootTree = &cacheEntry } else { @@ -159,6 +160,8 @@ func (bt *OldRebuiltForrest) RebuiltTree(treeID btrfsprim.ObjID) oldRebuiltTree return cacheEntry } +func discardOK[T any](x T, _ bool) T { return x } + func (bt *OldRebuiltForrest) rawTreeWalk(root btrfstree.TreeRoot, cacheEntry oldRebuiltTree, walked *[]btrfsprim.Key) { errHandle := func(err *btrfstree.TreeError) { if len(err.Path) > 0 && err.Path.Node(-1).ToNodeAddr == 0 { @@ -173,7 +176,32 @@ func (bt *OldRebuiltForrest) rawTreeWalk(root btrfstree.TreeRoot, cacheEntry old }) } + var curNode nodeInfo cbs := btrfstree.TreeWalkHandler{ + BadNode: func(path btrfstree.TreePath, 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.TreePath, 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.TreePath, 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 @@ -182,9 +210,11 @@ 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) @@ -217,6 +247,33 @@ func (tree oldRebuiltTree) addErrs(fn func(btrfsprim.Key, uint32) int, err error 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.Optional[btrfsvol.LogicalAddr]{OK: true, Val: nodeInfo.LAddr}, + Level: containers.Optional[uint8]{OK: true, Val: nodeInfo.Level}, + Generation: containers.Optional[btrfsprim.Generation]{OK: true, Val: 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.Optional[btrfsprim.Key]{OK: true, Val: nodeInfo.MinItem}, + MaxItem: containers.Optional[btrfsprim.Key]{OK: true, Val: 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 { @@ -230,14 +287,10 @@ 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)) } - itemPath := bt.arena.Inflate(indexItem.Value.Path) - node, err := bt.inner.ReadNode(itemPath.Parent()) + node := bt.readNode(indexItem.Value.Node) defer node.Free() - if err != nil { - return btrfstree.Item{}, fmt.Errorf("item with %s: %w", searcher, tree.addErrs(searcher.Search, err)) - } - item := node.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 @@ -266,18 +319,12 @@ func (bt *OldRebuiltForrest) TreeSearchAll(treeID btrfsprim.ObjID, searcher btrf ret := make([]btrfstree.Item, len(indexItems)) var node *btrfstree.Node - for i := range indexItems { - itemPath := bt.arena.Inflate(indexItems[i].Path) - if node == nil || node.Head.Addr != itemPath.Node(-2).ToNodeAddr { - var err error + for i, indexItem := range indexItems { + if node == nil || node.Head.Addr != indexItem.Node.LAddr { node.Free() - node, err = bt.inner.ReadNode(itemPath.Parent()) - if err != nil { - node.Free() - return nil, fmt.Errorf("items with %s: %w", searcher, tree.addErrs(searcher.Search, err)) - } + node = bt.readNode(indexItem.Node) } - ret[i] = node.BodyLeaf[itemPath.Node(-1).FromItemSlot] + ret[i] = node.BodyLeaf[indexItem.Slot] ret[i].Body = ret[i].Body.CloneItem() } node.Free() @@ -312,18 +359,28 @@ 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.Head.Addr != itemPath.Node(-2).ToNodeAddr { - var err error + if node == nil || node.Head.Addr != indexItem.Value.Node.LAddr { node.Free() - node, err = bt.inner.ReadNode(itemPath.Parent()) - if err != nil { - node.Free() - errHandle(&btrfstree.TreeError{Path: itemPath, Err: err}) - return true - } + node = bt.readNode(indexItem.Value.Node) + } + item := node.BodyLeaf[indexItem.Value.Slot] + + itemPath := btrfstree.TreePath{ + { + 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.BodyLeaf[itemPath.Node(-1).FromItemSlot] if err := cbs.Item(itemPath, item); err != nil { errHandle(&btrfstree.TreeError{Path: itemPath, Err: err}) } diff --git a/lib/btrfsutil/skinny_paths.go b/lib/btrfsutil/skinny_paths.go deleted file mode 100644 index 1361fff..0000000 --- a/lib/btrfsutil/skinny_paths.go +++ /dev/null @@ -1,146 +0,0 @@ -// Copyright (C) 2022-2023 Luke Shumaker -// -// 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[btrfsvol.LogicalAddr](a.FS, a.SB, parent.Node(-1).ToNodeAddr, btrfstree.NodeExpectations{}) - defer node.Free() - if err != nil { - return btrfstree.TreePathElem{}, err - } - if node.Head.Level > 0 { - if itemSlot >= len(node.BodyInterior) { - panic("should not happen") - } - for i, item := range node.BodyInterior { - toMaxKey := parent.Node(-1).ToMaxKey - if i+1 < len(node.BodyInterior) { - toMaxKey = node.BodyInterior[i+1].Key.Mm() - } - elem := btrfstree.TreePathElem{ - FromTree: node.Head.Owner, - FromItemSlot: i, - ToNodeAddr: item.BlockPtr, - ToNodeGeneration: item.Generation, - ToNodeLevel: node.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.BodyLeaf) { - panic("should not happen") - } - for i, item := range node.BodyLeaf { - elem := btrfstree.TreePathElem{ - FromTree: node.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 -} -- cgit v1.1-4-g5e80 From ec1b90339bf712d08c417d735faa4ef40e99d452 Mon Sep 17 00:00:00 2001 From: Luke Shumaker Date: Tue, 28 Feb 2023 19:21:37 -0700 Subject: rebuildmappings: Audit identifier names --- cmd/btrfs-rec/inspect/rebuildmappings/process.go | 10 ++++----- .../inspect/rebuildmappings/process_blockgroups.go | 10 ++++----- .../rebuildmappings/process_matchsums_exact.go | 10 ++++----- .../rebuildmappings/process_matchsums_fuzzy.go | 10 ++++----- .../rebuildmappings/process_sums_logical.go | 24 ++++++++++---------- .../rebuildmappings/process_sums_physical.go | 16 ++++++------- cmd/btrfs-rec/inspect/rebuildmappings/scan.go | 26 ++++++++++++---------- .../inspect/rebuildmappings/sumrunwithgaps.go | 24 ++++++++++---------- 8 files changed, 66 insertions(+), 64 deletions(-) diff --git a/cmd/btrfs-rec/inspect/rebuildmappings/process.go b/cmd/btrfs-rec/inspect/rebuildmappings/process.go index a93b697..e42acf9 100644 --- a/cmd/btrfs-rec/inspect/rebuildmappings/process.go +++ b/cmd/btrfs-rec/inspect/rebuildmappings/process.go @@ -117,7 +117,7 @@ func RebuildMappings(ctx context.Context, fs *btrfs.FS, scanResults ScanDevicesR // First dedup them, because they change for allocations and // CoW means that they'll bounce around a lot, so you likely // have oodles of duplicates? - bgs, err := DedupBlockGroups(scanResults) + bgs, err := dedupedBlockGroups(scanResults) if err != nil { return err } @@ -162,8 +162,8 @@ func RebuildMappings(ctx context.Context, fs *btrfs.FS, scanResults ScanDevicesR // slower. ctx = dlog.WithField(_ctx, "btrfs.inspect.rebuild-mappings.process.step", "5/6") dlog.Infof(_ctx, "5/6: Searching for %d block groups in checksum map (exact)...", len(bgs)) - physicalSums := ExtractPhysicalSums(scanResults) - logicalSums := ExtractLogicalSums(ctx, scanResults) + physicalSums := extractPhysicalSums(scanResults) + logicalSums := extractLogicalSums(ctx, scanResults) if err := matchBlockGroupSumsExact(ctx, fs, bgs, physicalSums, logicalSums); err != nil { return err } @@ -179,7 +179,7 @@ func RebuildMappings(ctx context.Context, fs *btrfs.FS, scanResults ScanDevicesR ctx = dlog.WithField(_ctx, "btrfs.inspect.rebuild-mappings.process.step", "report") dlog.Info(_ctx, "report:") - unmappedPhysicalRegions := ListUnmappedPhysicalRegions(fs) + unmappedPhysicalRegions := listUnmappedPhysicalRegions(fs) var unmappedPhysical btrfsvol.AddrDelta var numUnmappedPhysical int for _, devRegions := range unmappedPhysicalRegions { @@ -190,7 +190,7 @@ func RebuildMappings(ctx context.Context, fs *btrfs.FS, scanResults ScanDevicesR } dlog.Infof(ctx, "... %d of unmapped physical space (across %d regions)", textui.IEC(unmappedPhysical, "B"), numUnmappedPhysical) - unmappedLogicalRegions := ListUnmappedLogicalRegions(fs, logicalSums) + unmappedLogicalRegions := listUnmappedLogicalRegions(fs, logicalSums) var unmappedLogical btrfsvol.AddrDelta for _, region := range unmappedLogicalRegions { unmappedLogical += region.Size() diff --git a/cmd/btrfs-rec/inspect/rebuildmappings/process_blockgroups.go b/cmd/btrfs-rec/inspect/rebuildmappings/process_blockgroups.go index f8d2337..e7cdf0e 100644 --- a/cmd/btrfs-rec/inspect/rebuildmappings/process_blockgroups.go +++ b/cmd/btrfs-rec/inspect/rebuildmappings/process_blockgroups.go @@ -13,18 +13,18 @@ import ( "git.lukeshu.com/btrfs-progs-ng/lib/maps" ) -type BlockGroup struct { +type blockGroup struct { LAddr btrfsvol.LogicalAddr Size btrfsvol.AddrDelta Flags btrfsvol.BlockGroupFlags } -func DedupBlockGroups(scanResults ScanDevicesResult) (map[btrfsvol.LogicalAddr]BlockGroup, error) { +func dedupedBlockGroups(scanResults ScanDevicesResult) (map[btrfsvol.LogicalAddr]blockGroup, error) { // Dedup - bgsSet := make(containers.Set[BlockGroup]) + bgsSet := make(containers.Set[blockGroup]) for _, devResults := range scanResults { for _, bg := range devResults.FoundBlockGroups { - bgsSet.Insert(BlockGroup{ + bgsSet.Insert(blockGroup{ LAddr: btrfsvol.LogicalAddr(bg.Key.ObjectID), Size: btrfsvol.AddrDelta(bg.Key.Offset), Flags: bg.BG.Flags, @@ -49,7 +49,7 @@ func DedupBlockGroups(scanResults ScanDevicesResult) (map[btrfsvol.LogicalAddr]B // Return. We return a map instead of a slice in order to // facilitate easy deletes. - bgsMap := make(map[btrfsvol.LogicalAddr]BlockGroup, len(bgsSet)) + bgsMap := make(map[btrfsvol.LogicalAddr]blockGroup, len(bgsSet)) for bg := range bgsSet { bgsMap[bg.LAddr] = bg } diff --git a/cmd/btrfs-rec/inspect/rebuildmappings/process_matchsums_exact.go b/cmd/btrfs-rec/inspect/rebuildmappings/process_matchsums_exact.go index 533ae67..ef9d9aa 100644 --- a/cmd/btrfs-rec/inspect/rebuildmappings/process_matchsums_exact.go +++ b/cmd/btrfs-rec/inspect/rebuildmappings/process_matchsums_exact.go @@ -19,15 +19,15 @@ import ( func matchBlockGroupSumsExact(ctx context.Context, fs *btrfs.FS, - blockgroups map[btrfsvol.LogicalAddr]BlockGroup, + blockgroups map[btrfsvol.LogicalAddr]blockGroup, physicalSums map[btrfsvol.DeviceID]btrfssum.SumRun[btrfsvol.PhysicalAddr], - logicalSums SumRunWithGaps[btrfsvol.LogicalAddr], + logicalSums sumRunWithGaps[btrfsvol.LogicalAddr], ) error { - regions := ListUnmappedPhysicalRegions(fs) + regions := listUnmappedPhysicalRegions(fs) numBlockgroups := len(blockgroups) for i, bgLAddr := range maps.SortedKeys(blockgroups) { blockgroup := blockgroups[bgLAddr] - bgRun := SumsForLogicalRegion(logicalSums, blockgroup.LAddr, blockgroup.Size) + bgRun := sumsForLogicalRegion(logicalSums, blockgroup.LAddr, blockgroup.Size) if len(bgRun.Runs) == 0 { dlog.Errorf(ctx, "(%v/%v) blockgroup[laddr=%v] can't be matched because it has 0 runs", i+1, numBlockgroups, bgLAddr) @@ -35,7 +35,7 @@ func matchBlockGroupSumsExact(ctx context.Context, } var matches []btrfsvol.QualifiedPhysicalAddr - if err := WalkUnmappedPhysicalRegions(ctx, physicalSums, regions, func(devID btrfsvol.DeviceID, region btrfssum.SumRun[btrfsvol.PhysicalAddr]) error { + if err := walkUnmappedPhysicalRegions(ctx, physicalSums, regions, func(devID btrfsvol.DeviceID, region btrfssum.SumRun[btrfsvol.PhysicalAddr]) error { rawMatches := indexAll[int, btrfssum.ShortSum](region, bgRun) for _, match := range rawMatches { matches = append(matches, btrfsvol.QualifiedPhysicalAddr{ diff --git a/cmd/btrfs-rec/inspect/rebuildmappings/process_matchsums_fuzzy.go b/cmd/btrfs-rec/inspect/rebuildmappings/process_matchsums_fuzzy.go index 00f367f..905211c 100644 --- a/cmd/btrfs-rec/inspect/rebuildmappings/process_matchsums_fuzzy.go +++ b/cmd/btrfs-rec/inspect/rebuildmappings/process_matchsums_fuzzy.go @@ -39,17 +39,17 @@ func (a fuzzyRecord) Compare(b fuzzyRecord) int { func matchBlockGroupSumsFuzzy(ctx context.Context, fs *btrfs.FS, - blockgroups map[btrfsvol.LogicalAddr]BlockGroup, + blockgroups map[btrfsvol.LogicalAddr]blockGroup, physicalSums map[btrfsvol.DeviceID]btrfssum.SumRun[btrfsvol.PhysicalAddr], - logicalSums SumRunWithGaps[btrfsvol.LogicalAddr], + logicalSums sumRunWithGaps[btrfsvol.LogicalAddr], ) error { _ctx := ctx ctx = dlog.WithField(_ctx, "btrfs.inspect.rebuild-mappings.process.substep", "indexing") dlog.Info(ctx, "Indexing physical regions...") // O(m) - regions := ListUnmappedPhysicalRegions(fs) + regions := listUnmappedPhysicalRegions(fs) physicalIndex := make(map[btrfssum.ShortSum][]btrfsvol.QualifiedPhysicalAddr) - if err := WalkUnmappedPhysicalRegions(ctx, physicalSums, regions, func(devID btrfsvol.DeviceID, region btrfssum.SumRun[btrfsvol.PhysicalAddr]) error { + if err := walkUnmappedPhysicalRegions(ctx, physicalSums, regions, func(devID btrfsvol.DeviceID, region btrfssum.SumRun[btrfsvol.PhysicalAddr]) error { return region.Walk(ctx, func(paddr btrfsvol.PhysicalAddr, sum btrfssum.ShortSum) error { physicalIndex[sum] = append(physicalIndex[sum], btrfsvol.QualifiedPhysicalAddr{ Dev: devID, @@ -67,7 +67,7 @@ func matchBlockGroupSumsFuzzy(ctx context.Context, numBlockgroups := len(blockgroups) for i, bgLAddr := range maps.SortedKeys(blockgroups) { blockgroup := blockgroups[bgLAddr] - bgRun := SumsForLogicalRegion(logicalSums, blockgroup.LAddr, blockgroup.Size) + bgRun := sumsForLogicalRegion(logicalSums, blockgroup.LAddr, blockgroup.Size) d := bgRun.PatLen() matches := make(map[btrfsvol.QualifiedPhysicalAddr]int) diff --git a/cmd/btrfs-rec/inspect/rebuildmappings/process_sums_logical.go b/cmd/btrfs-rec/inspect/rebuildmappings/process_sums_logical.go index 2cdabb7..52f8252 100644 --- a/cmd/btrfs-rec/inspect/rebuildmappings/process_sums_logical.go +++ b/cmd/btrfs-rec/inspect/rebuildmappings/process_sums_logical.go @@ -19,8 +19,8 @@ import ( "git.lukeshu.com/btrfs-progs-ng/lib/slices" ) -func ExtractLogicalSums(ctx context.Context, scanResults ScanDevicesResult) SumRunWithGaps[btrfsvol.LogicalAddr] { - var records []SysExtentCSum +func extractLogicalSums(ctx context.Context, scanResults ScanDevicesResult) sumRunWithGaps[btrfsvol.LogicalAddr] { + var records []FoundExtentCSum for _, devResults := range scanResults { records = append(records, devResults.FoundExtentCSums...) } @@ -37,7 +37,7 @@ func ExtractLogicalSums(ctx context.Context, scanResults ScanDevicesResult) SumR } }) if len(records) == 0 { - return SumRunWithGaps[btrfsvol.LogicalAddr]{} + return sumRunWithGaps[btrfsvol.LogicalAddr]{} } sumSize := records[0].Sums.ChecksumSize @@ -52,10 +52,10 @@ func ExtractLogicalSums(ctx context.Context, scanResults ScanDevicesResult) SumR // "AAAAAAA" shouldn't be present, and if we just discard "BBBBBBBB" // because it conflicts with "CCCCCCC", then we would erroneously // include "AAAAAAA". - addrspace := new(containers.RBTree[SysExtentCSum]) + addrspace := new(containers.RBTree[FoundExtentCSum]) for _, newRecord := range records { for { - conflict := addrspace.Search(func(oldRecord SysExtentCSum) int { + conflict := addrspace.Search(func(oldRecord FoundExtentCSum) int { switch { case newRecord.Sums.Addr.Add(newRecord.Sums.Size()) <= oldRecord.Sums.Addr: // 'newRecord' is wholly to the left of 'oldRecord'. @@ -127,7 +127,7 @@ func ExtractLogicalSums(ctx context.Context, scanResults ScanDevicesResult) SumR case newRecord.Sums.Addr.Add(newRecord.Sums.Size()) > overlapEnd: suffix = newRecord.Sums.Sums[newOverlapEnd:] } - unionRecord := SysExtentCSum{ + unionRecord := FoundExtentCSum{ Generation: oldRecord.Generation, Sums: btrfsitem.ExtentCSum{ SumRun: btrfssum.SumRun[btrfsvol.LogicalAddr]{ @@ -143,11 +143,11 @@ func ExtractLogicalSums(ctx context.Context, scanResults ScanDevicesResult) SumR } } - // Now flatten that RBTree in to a SumRunWithGaps. - var flattened SumRunWithGaps[btrfsvol.LogicalAddr] + // Now flatten that RBTree in to a sumRunWithGaps. + var flattened sumRunWithGaps[btrfsvol.LogicalAddr] var curAddr btrfsvol.LogicalAddr var curSums strings.Builder - addrspace.Range(func(node *containers.RBNode[SysExtentCSum]) bool { + addrspace.Range(func(node *containers.RBNode[FoundExtentCSum]) bool { curEnd := curAddr + (btrfsvol.LogicalAddr(curSums.Len()/sumSize) * btrfssum.BlockSize) if node.Value.Sums.Addr != curEnd { if curSums.Len() > 0 { @@ -178,7 +178,7 @@ func ExtractLogicalSums(ctx context.Context, scanResults ScanDevicesResult) SumR return flattened } -func ListUnmappedLogicalRegions(fs *btrfs.FS, logicalSums SumRunWithGaps[btrfsvol.LogicalAddr]) []btrfssum.SumRun[btrfsvol.LogicalAddr] { +func listUnmappedLogicalRegions(fs *btrfs.FS, logicalSums sumRunWithGaps[btrfsvol.LogicalAddr]) []btrfssum.SumRun[btrfsvol.LogicalAddr] { // There are a lot of ways this algorithm could be made // faster. var ret []btrfssum.SumRun[btrfsvol.LogicalAddr] @@ -221,8 +221,8 @@ func ListUnmappedLogicalRegions(fs *btrfs.FS, logicalSums SumRunWithGaps[btrfsvo return ret } -func SumsForLogicalRegion(sums SumRunWithGaps[btrfsvol.LogicalAddr], beg btrfsvol.LogicalAddr, size btrfsvol.AddrDelta) SumRunWithGaps[btrfsvol.LogicalAddr] { - runs := SumRunWithGaps[btrfsvol.LogicalAddr]{ +func sumsForLogicalRegion(sums sumRunWithGaps[btrfsvol.LogicalAddr], beg btrfsvol.LogicalAddr, size btrfsvol.AddrDelta) sumRunWithGaps[btrfsvol.LogicalAddr] { + runs := sumRunWithGaps[btrfsvol.LogicalAddr]{ Addr: beg, Size: size, } diff --git a/cmd/btrfs-rec/inspect/rebuildmappings/process_sums_physical.go b/cmd/btrfs-rec/inspect/rebuildmappings/process_sums_physical.go index 392ded9..5f8d932 100644 --- a/cmd/btrfs-rec/inspect/rebuildmappings/process_sums_physical.go +++ b/cmd/btrfs-rec/inspect/rebuildmappings/process_sums_physical.go @@ -16,7 +16,7 @@ import ( "git.lukeshu.com/btrfs-progs-ng/lib/maps" ) -func ExtractPhysicalSums(scanResults ScanDevicesResult) map[btrfsvol.DeviceID]btrfssum.SumRun[btrfsvol.PhysicalAddr] { +func extractPhysicalSums(scanResults ScanDevicesResult) map[btrfsvol.DeviceID]btrfssum.SumRun[btrfsvol.PhysicalAddr] { ret := make(map[btrfsvol.DeviceID]btrfssum.SumRun[btrfsvol.PhysicalAddr], len(scanResults)) for devID, devResults := range scanResults { ret[devID] = devResults.Checksums @@ -24,12 +24,12 @@ func ExtractPhysicalSums(scanResults ScanDevicesResult) map[btrfsvol.DeviceID]bt return ret } -type PhysicalRegion struct { +type physicalRegion struct { Beg, End btrfsvol.PhysicalAddr } -func ListUnmappedPhysicalRegions(fs *btrfs.FS) map[btrfsvol.DeviceID][]PhysicalRegion { - regions := make(map[btrfsvol.DeviceID][]PhysicalRegion) +func listUnmappedPhysicalRegions(fs *btrfs.FS) map[btrfsvol.DeviceID][]physicalRegion { + regions := make(map[btrfsvol.DeviceID][]physicalRegion) pos := make(map[btrfsvol.DeviceID]btrfsvol.PhysicalAddr) mappings := fs.LV.Mappings() sort.Slice(mappings, func(i, j int) bool { @@ -37,7 +37,7 @@ func ListUnmappedPhysicalRegions(fs *btrfs.FS) map[btrfsvol.DeviceID][]PhysicalR }) for _, mapping := range mappings { if pos[mapping.PAddr.Dev] < mapping.PAddr.Addr { - regions[mapping.PAddr.Dev] = append(regions[mapping.PAddr.Dev], PhysicalRegion{ + regions[mapping.PAddr.Dev] = append(regions[mapping.PAddr.Dev], physicalRegion{ Beg: pos[mapping.PAddr.Dev], End: mapping.PAddr.Addr, }) @@ -49,7 +49,7 @@ func ListUnmappedPhysicalRegions(fs *btrfs.FS) map[btrfsvol.DeviceID][]PhysicalR for devID, dev := range fs.LV.PhysicalVolumes() { devSize := dev.Size() if pos[devID] < devSize { - regions[devID] = append(regions[devID], PhysicalRegion{ + regions[devID] = append(regions[devID], physicalRegion{ Beg: pos[devID], End: devSize, }) @@ -62,9 +62,9 @@ func roundUp[T constraints.Integer](x, multiple T) T { return ((x + multiple - 1) / multiple) * multiple } -func WalkUnmappedPhysicalRegions(ctx context.Context, +func walkUnmappedPhysicalRegions(ctx context.Context, physicalSums map[btrfsvol.DeviceID]btrfssum.SumRun[btrfsvol.PhysicalAddr], - gaps map[btrfsvol.DeviceID][]PhysicalRegion, + gaps map[btrfsvol.DeviceID][]physicalRegion, fn func(btrfsvol.DeviceID, btrfssum.SumRun[btrfsvol.PhysicalAddr]) error, ) error { for _, devID := range maps.SortedKeys(gaps) { diff --git a/cmd/btrfs-rec/inspect/rebuildmappings/scan.go b/cmd/btrfs-rec/inspect/rebuildmappings/scan.go index e23314e..76d8a75 100644 --- a/cmd/btrfs-rec/inspect/rebuildmappings/scan.go +++ b/cmd/btrfs-rec/inspect/rebuildmappings/scan.go @@ -29,29 +29,31 @@ type ScanDevicesResult = map[btrfsvol.DeviceID]ScanOneDeviceResult type ScanOneDeviceResult struct { Checksums btrfssum.SumRun[btrfsvol.PhysicalAddr] FoundNodes map[btrfsvol.LogicalAddr][]btrfsvol.PhysicalAddr - FoundChunks []btrfstree.SysChunk - FoundBlockGroups []SysBlockGroup - FoundDevExtents []SysDevExtent - FoundExtentCSums []SysExtentCSum + FoundChunks []FoundChunk + FoundBlockGroups []FoundBlockGroup + FoundDevExtents []FoundDevExtent + FoundExtentCSums []FoundExtentCSum } -type SysBlockGroup struct { +type FoundChunk = btrfstree.SysChunk + +type FoundBlockGroup struct { Key btrfsprim.Key BG btrfsitem.BlockGroup } -type SysDevExtent struct { +type FoundDevExtent struct { Key btrfsprim.Key DevExt btrfsitem.DevExtent } -type SysExtentCSum struct { +type FoundExtentCSum struct { Generation btrfsprim.Generation Sums btrfsitem.ExtentCSum } // Compare implements containers.Ordered. -func (a SysExtentCSum) Compare(b SysExtentCSum) int { +func (a FoundExtentCSum) Compare(b FoundExtentCSum) int { return containers.NativeCompare(a.Sums.Addr, b.Sums.Addr) } @@ -129,7 +131,7 @@ func (scanner *deviceScanner) ScanNode(ctx context.Context, addr btrfsvol.Physic case *btrfsitem.Chunk: dlog.Tracef(ctx, "node@%v: item %v: found chunk", addr, i) - scanner.result.FoundChunks = append(scanner.result.FoundChunks, btrfstree.SysChunk{ + scanner.result.FoundChunks = append(scanner.result.FoundChunks, FoundChunk{ Key: item.Key, Chunk: *itemBody, }) @@ -144,7 +146,7 @@ func (scanner *deviceScanner) ScanNode(ctx context.Context, addr btrfsvol.Physic case *btrfsitem.BlockGroup: dlog.Tracef(ctx, "node@%v: item %v: found block group", addr, i) - scanner.result.FoundBlockGroups = append(scanner.result.FoundBlockGroups, SysBlockGroup{ + scanner.result.FoundBlockGroups = append(scanner.result.FoundBlockGroups, FoundBlockGroup{ Key: item.Key, BG: *itemBody, }) @@ -159,7 +161,7 @@ func (scanner *deviceScanner) ScanNode(ctx context.Context, addr btrfsvol.Physic case *btrfsitem.DevExtent: dlog.Tracef(ctx, "node@%v: item %v: found dev extent", addr, i) - scanner.result.FoundDevExtents = append(scanner.result.FoundDevExtents, SysDevExtent{ + scanner.result.FoundDevExtents = append(scanner.result.FoundDevExtents, FoundDevExtent{ Key: item.Key, DevExt: *itemBody, }) @@ -174,7 +176,7 @@ func (scanner *deviceScanner) ScanNode(ctx context.Context, addr btrfsvol.Physic case *btrfsitem.ExtentCSum: dlog.Tracef(ctx, "node@%v: item %v: found csums", addr, i) - scanner.result.FoundExtentCSums = append(scanner.result.FoundExtentCSums, SysExtentCSum{ + scanner.result.FoundExtentCSums = append(scanner.result.FoundExtentCSums, FoundExtentCSum{ Generation: node.Head.Generation, Sums: *itemBody, }) diff --git a/cmd/btrfs-rec/inspect/rebuildmappings/sumrunwithgaps.go b/cmd/btrfs-rec/inspect/rebuildmappings/sumrunwithgaps.go index f79e2be..3522b3e 100644 --- a/cmd/btrfs-rec/inspect/rebuildmappings/sumrunwithgaps.go +++ b/cmd/btrfs-rec/inspect/rebuildmappings/sumrunwithgaps.go @@ -17,7 +17,7 @@ import ( "git.lukeshu.com/btrfs-progs-ng/lib/slices" ) -type SumRunWithGaps[Addr btrfsvol.IntAddr[Addr]] struct { +type sumRunWithGaps[Addr btrfsvol.IntAddr[Addr]] struct { // Store the start address and size, in order to facilitate // leading and trailing gaps. Addr Addr @@ -27,16 +27,16 @@ type SumRunWithGaps[Addr btrfsvol.IntAddr[Addr]] struct { } var ( - _ lowmemjson.Encodable = SumRunWithGaps[btrfsvol.LogicalAddr]{} - _ lowmemjson.Decodable = (*SumRunWithGaps[btrfsvol.LogicalAddr])(nil) + _ lowmemjson.Encodable = sumRunWithGaps[btrfsvol.LogicalAddr]{} + _ lowmemjson.Decodable = (*sumRunWithGaps[btrfsvol.LogicalAddr])(nil) ) // PatLen implements kmpPattern[int, ShortSum]. -func (sg SumRunWithGaps[Addr]) PatLen() int { +func (sg sumRunWithGaps[Addr]) PatLen() int { return int(sg.Size / btrfssum.BlockSize) } -func (sg SumRunWithGaps[Addr]) PctFull() float64 { +func (sg sumRunWithGaps[Addr]) PctFull() float64 { total := sg.PatLen() var full int for _, run := range sg.Runs { @@ -45,7 +45,7 @@ func (sg SumRunWithGaps[Addr]) PctFull() float64 { return float64(full) / float64(total) } -func (sg SumRunWithGaps[Addr]) RunForAddr(addr Addr) (btrfssum.SumRun[Addr], Addr, bool) { +func (sg sumRunWithGaps[Addr]) RunForAddr(addr Addr) (btrfssum.SumRun[Addr], Addr, bool) { for _, run := range sg.Runs { if run.Addr > addr { return btrfssum.SumRun[Addr]{}, run.Addr, false @@ -58,7 +58,7 @@ func (sg SumRunWithGaps[Addr]) RunForAddr(addr Addr) (btrfssum.SumRun[Addr], Add return btrfssum.SumRun[Addr]{}, math.MaxInt64, false } -func (sg SumRunWithGaps[Addr]) SumForAddr(addr Addr) (btrfssum.ShortSum, bool) { +func (sg sumRunWithGaps[Addr]) SumForAddr(addr Addr) (btrfssum.ShortSum, bool) { if addr < sg.Addr || addr >= sg.Addr.Add(sg.Size) { return "", false } @@ -80,7 +80,7 @@ func (sg SumRunWithGaps[Addr]) SumForAddr(addr Addr) (btrfssum.ShortSum, bool) { return run.Sums[off : off+run.ChecksumSize], true } -func (sg SumRunWithGaps[Addr]) Walk(ctx context.Context, fn func(Addr, btrfssum.ShortSum) error) error { +func (sg sumRunWithGaps[Addr]) Walk(ctx context.Context, fn func(Addr, btrfssum.ShortSum) error) error { for _, run := range sg.Runs { if err := run.Walk(ctx, fn); err != nil { return err @@ -90,12 +90,12 @@ func (sg SumRunWithGaps[Addr]) Walk(ctx context.Context, fn func(Addr, btrfssum. } // PatGet implements kmpPattern[int, ShortSum]. -func (sg SumRunWithGaps[Addr]) PatGet(sumIdx int) (btrfssum.ShortSum, bool) { +func (sg sumRunWithGaps[Addr]) PatGet(sumIdx int) (btrfssum.ShortSum, bool) { addr := sg.Addr.Add(btrfsvol.AddrDelta(sumIdx) * btrfssum.BlockSize) return sg.SumForAddr(addr) } -func (sg SumRunWithGaps[Addr]) EncodeJSON(w io.Writer) error { +func (sg sumRunWithGaps[Addr]) EncodeJSON(w io.Writer) error { if _, err := fmt.Fprintf(w, `{"Addr":%d,"Size":%d,"Runs":[`, sg.Addr, sg.Size); err != nil { return err } @@ -136,8 +136,8 @@ func (sg SumRunWithGaps[Addr]) EncodeJSON(w io.Writer) error { return nil } -func (sg *SumRunWithGaps[Addr]) DecodeJSON(r io.RuneScanner) error { - *sg = SumRunWithGaps[Addr]{} +func (sg *sumRunWithGaps[Addr]) DecodeJSON(r io.RuneScanner) error { + *sg = sumRunWithGaps[Addr]{} var name string return lowmemjson.DecodeObject(r, func(r io.RuneScanner) error { -- cgit v1.1-4-g5e80 From d7a616119a4f5fbfa8d0f028e337037a48272048 Mon Sep 17 00:00:00 2001 From: Luke Shumaker Date: Tue, 28 Feb 2023 23:50:32 -0700 Subject: rebuildtrees: Move item-data from btrfsutil.KeyIO to scan --- cmd/btrfs-rec/inspect/rebuildtrees/rebuild.go | 20 ++--- .../inspect/rebuildtrees/rebuild_wantcb.go | 8 +- cmd/btrfs-rec/inspect/rebuildtrees/scan.go | 97 +++++++++++++++++++--- lib/btrfsutil/graph.go | 4 +- lib/btrfsutil/rebuilt_readitem.go | 69 +-------------- 5 files changed, 103 insertions(+), 95 deletions(-) diff --git a/cmd/btrfs-rec/inspect/rebuildtrees/rebuild.go b/cmd/btrfs-rec/inspect/rebuildtrees/rebuild.go index ca1ce8c..c1391eb 100644 --- a/cmd/btrfs-rec/inspect/rebuildtrees/rebuild.go +++ b/cmd/btrfs-rec/inspect/rebuildtrees/rebuild.go @@ -47,8 +47,7 @@ func (o keyAndTree) String() string { } type rebuilder struct { - sb btrfstree.Superblock - graph btrfsutil.Graph + scan ScanDevicesResult keyIO *btrfsutil.KeyIO rebuilt *btrfsutil.RebuiltForrest @@ -79,17 +78,18 @@ type Rebuilder interface { func NewRebuilder(ctx context.Context, fs *btrfs.FS, nodeList []btrfsvol.LogicalAddr) (Rebuilder, error) { ctx = dlog.WithField(ctx, "btrfs.inspect.rebuild-trees.step", "read-fs-data") - sb, nodeGraph, keyIO, err := ScanDevices(ctx, fs, nodeList) // ScanDevices does its own logging + scanData, err := ScanDevices(ctx, fs, nodeList) // ScanDevices does its own logging if err != nil { return nil, err } + keyIO := btrfsutil.NewKeyIO(fs, scanData.Superblock, scanData.Graph) + o := &rebuilder{ - sb: sb, - graph: nodeGraph, + scan: scanData, keyIO: keyIO, } - o.rebuilt = btrfsutil.NewRebuiltForrest(sb, nodeGraph, keyIO, o) + o.rebuilt = btrfsutil.NewRebuiltForrest(scanData.Superblock, scanData.Graph, keyIO, o) return o, nil } @@ -385,8 +385,8 @@ func (o *rebuilder) resolveTreeAugments(ctx context.Context, treeID btrfsprim.Ob } else { choices[choice] = ChoiceInfo{ Count: 1, - Distance: discardOK(o.rebuilt.Tree(ctx, treeID).COWDistance(o.graph.Nodes[choice].Owner)), - Generation: o.graph.Nodes[choice].Generation, + Distance: discardOK(o.rebuilt.Tree(ctx, treeID).COWDistance(o.scan.Graph.Nodes[choice].Owner)), + Generation: o.scan.Graph.Nodes[choice].Generation, } } } @@ -399,8 +399,8 @@ func (o *rebuilder) resolveTreeAugments(ctx context.Context, treeID btrfsprim.Ob } else { choices[choice] = ChoiceInfo{ Count: 1, - Distance: discardOK(o.rebuilt.Tree(ctx, treeID).COWDistance(o.graph.Nodes[choice].Owner)), - Generation: o.graph.Nodes[choice].Generation, + Distance: discardOK(o.rebuilt.Tree(ctx, treeID).COWDistance(o.scan.Graph.Nodes[choice].Owner)), + Generation: o.scan.Graph.Nodes[choice].Generation, } } } diff --git a/cmd/btrfs-rec/inspect/rebuildtrees/rebuild_wantcb.go b/cmd/btrfs-rec/inspect/rebuildtrees/rebuild_wantcb.go index 704f4ee..78ed8ab 100644 --- a/cmd/btrfs-rec/inspect/rebuildtrees/rebuild_wantcb.go +++ b/cmd/btrfs-rec/inspect/rebuildtrees/rebuild_wantcb.go @@ -145,7 +145,7 @@ func (o *rebuilder) WantDirIndex(ctx context.Context, reason string, treeID btrf return tgt.Compare(key) }, func(_ btrfsprim.Key, ptr btrfsutil.ItemPtr) bool { - if itemName, ok := o.keyIO.Names[ptr]; ok && bytes.Equal(itemName, name) { + if itemName, ok := o.scan.Names[ptr]; ok && bytes.Equal(itemName, name) { found = true } return !found @@ -166,7 +166,7 @@ func (o *rebuilder) WantDirIndex(ctx context.Context, reason string, treeID btrf return tgt.Compare(key) }, func(_ btrfsprim.Key, ptr btrfsutil.ItemPtr) bool { - if itemName, ok := o.keyIO.Names[ptr]; ok && bytes.Equal(itemName, name) { + if itemName, ok := o.scan.Names[ptr]; ok && bytes.Equal(itemName, name) { wants.InsertFrom(o.rebuilt.Tree(ctx, treeID).LeafToRoots(ctx, ptr.Node)) } return true @@ -203,7 +203,7 @@ func (o *rebuilder) _walkRange( } }, func(runKey btrfsprim.Key, runPtr btrfsutil.ItemPtr) bool { - runSizeAndErr, ok := o.keyIO.Sizes[runPtr] + runSizeAndErr, ok := o.scan.Sizes[runPtr] if !ok { panic(fmt.Errorf("should not happen: %v (%v) did not have a size recorded", runPtr, keyAndTree{TreeID: treeID, Key: runKey})) @@ -372,7 +372,7 @@ func (o *rebuilder) WantCSum(ctx context.Context, reason string, inodeTree, inod if !ok { panic(fmt.Errorf("should not happen: could not load key: %v", inodeWant)) } - inodeFlags, ok := o.keyIO.Flags[inodePtr] + inodeFlags, ok := o.scan.Flags[inodePtr] if !ok { panic(fmt.Errorf("should not happen: INODE_ITEM did not have flags recorded")) } diff --git a/cmd/btrfs-rec/inspect/rebuildtrees/scan.go b/cmd/btrfs-rec/inspect/rebuildtrees/scan.go index 4bc09ad..961ff8d 100644 --- a/cmd/btrfs-rec/inspect/rebuildtrees/scan.go +++ b/cmd/btrfs-rec/inspect/rebuildtrees/scan.go @@ -6,11 +6,14 @@ package rebuildtrees import ( "context" + "fmt" "time" "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" "git.lukeshu.com/btrfs-progs-ng/lib/btrfsutil" @@ -18,11 +21,31 @@ import ( "git.lukeshu.com/btrfs-progs-ng/lib/textui" ) -func ScanDevices(ctx context.Context, fs *btrfs.FS, nodeList []btrfsvol.LogicalAddr) (btrfstree.Superblock, btrfsutil.Graph, *btrfsutil.KeyIO, error) { +type SizeAndErr struct { + Size uint64 + Err error +} + +type FlagsAndErr struct { + NoDataSum bool + Err error +} + +type ScanDevicesResult struct { + Superblock btrfstree.Superblock + + Graph btrfsutil.Graph + + Flags map[btrfsutil.ItemPtr]FlagsAndErr // INODE_ITEM + Names map[btrfsutil.ItemPtr][]byte // DIR_INDEX + Sizes map[btrfsutil.ItemPtr]SizeAndErr // EXTENT_CSUM and EXTENT_DATA +} + +func ScanDevices(ctx context.Context, fs *btrfs.FS, nodeList []btrfsvol.LogicalAddr) (ScanDevicesResult, error) { dlog.Info(ctx, "Reading superblock...") sb, err := fs.Superblock() if err != nil { - return btrfstree.Superblock{}, btrfsutil.Graph{}, nil, err + return ScanDevicesResult{}, err } dlog.Infof(ctx, "Reading node data from FS...") @@ -33,24 +56,30 @@ func ScanDevices(ctx context.Context, fs *btrfs.FS, nodeList []btrfsvol.LogicalA dlog.WithField(ctx, "btrfs.inspect.rebuild-trees.read.substep", "read-nodes"), dlog.LogLevelInfo, textui.Tunable(1*time.Second)) - nodeGraph := btrfsutil.NewGraph(*sb) - keyIO := btrfsutil.NewKeyIO(fs, *sb) + ret := ScanDevicesResult{ + Superblock: *sb, + + Graph: btrfsutil.NewGraph(*sb), + + Flags: make(map[btrfsutil.ItemPtr]FlagsAndErr), + Names: make(map[btrfsutil.ItemPtr][]byte), + Sizes: make(map[btrfsutil.ItemPtr]SizeAndErr), + } progressWriter.Set(stats) for _, laddr := range nodeList { if err := ctx.Err(); err != nil { - return btrfstree.Superblock{}, btrfsutil.Graph{}, nil, err + return ScanDevicesResult{}, err } node, err := btrfstree.ReadNode[btrfsvol.LogicalAddr](fs, *sb, laddr, btrfstree.NodeExpectations{ LAddr: containers.Optional[btrfsvol.LogicalAddr]{OK: true, Val: laddr}, }) if err != nil { node.Free() - return btrfstree.Superblock{}, btrfsutil.Graph{}, nil, err + return ScanDevicesResult{}, err } - nodeGraph.InsertNode(node) - keyIO.InsertNode(node) + ret.insertNode(node) node.Free() @@ -64,10 +93,54 @@ func ScanDevices(ctx context.Context, fs *btrfs.FS, nodeList []btrfsvol.LogicalA dlog.Info(ctx, "... done reading node data") ctx = dlog.WithField(ctx, "btrfs.inspect.rebuild-trees.read.substep", "check") - if err := nodeGraph.FinalCheck(ctx, fs, *sb); err != nil { - return btrfstree.Superblock{}, btrfsutil.Graph{}, nil, err + if err := ret.Graph.FinalCheck(ctx, fs, *sb); err != nil { + return ScanDevicesResult{}, err } - keyIO.SetGraph(*nodeGraph) - return *sb, *nodeGraph, keyIO, nil + return ret, nil +} + +func (o *ScanDevicesResult) insertNode(node *btrfstree.Node) { + o.Graph.InsertNode(node) + for i, item := range node.BodyLeaf { + ptr := btrfsutil.ItemPtr{ + Node: node.Head.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, node.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, node.Head.Owner, item.Key, itemBody.Err), + } + } + } + } } diff --git a/lib/btrfsutil/graph.go b/lib/btrfsutil/graph.go index a7c299a..45e9878 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), diff --git a/lib/btrfsutil/rebuilt_readitem.go b/lib/btrfsutil/rebuilt_readitem.go index b1a0656..7e9be09 100644 --- a/lib/btrfsutil/rebuilt_readitem.go +++ b/lib/btrfsutil/rebuilt_readitem.go @@ -29,37 +29,20 @@ 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, *btrfstree.Node] } -func NewKeyIO(file diskio.File[btrfsvol.LogicalAddr], sb btrfstree.Superblock) *KeyIO { +func NewKeyIO(file diskio.File[btrfsvol.LogicalAddr], sb btrfstree.Superblock, graph Graph) *KeyIO { return &KeyIO{ rawFile: file, sb: sb, - - Flags: make(map[ItemPtr]FlagsAndErr), - Names: make(map[ItemPtr][]byte), - Sizes: make(map[ItemPtr]SizeAndErr), + graph: graph, cache: containers.ARCache[btrfsvol.LogicalAddr, *btrfstree.Node]{ MaxLen: textui.Tunable(8), @@ -70,54 +53,6 @@ func NewKeyIO(file diskio.File[btrfsvol.LogicalAddr], sb btrfstree.Superblock) * } } -func (o *KeyIO) InsertNode(node *btrfstree.Node) { - for i, item := range node.BodyLeaf { - ptr := ItemPtr{ - Node: node.Head.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, node.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, node.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) *btrfstree.Node { if cached, ok := o.cache.Load(laddr); ok { dlog.Tracef(ctx, "cache-hit node@%v", laddr) -- cgit v1.1-4-g5e80 From 41939480a14b2bb06622d72b9445aa14a9e3b451 Mon Sep 17 00:00:00 2001 From: Luke Shumaker Date: Wed, 1 Mar 2023 00:05:26 -0700 Subject: rebuildtrees: Be careful about what methods are exported --- cmd/btrfs-rec/inspect/rebuildtrees/rebuild.go | 4 ++-- cmd/btrfs-rec/inspect/rebuildtrees/rebuild_treecb.go | 16 ++++++++++------ cmd/btrfs-rec/inspect/rebuildtrees/rebuild_wantcb.go | 20 ++++++++++++-------- 3 files changed, 24 insertions(+), 16 deletions(-) diff --git a/cmd/btrfs-rec/inspect/rebuildtrees/rebuild.go b/cmd/btrfs-rec/inspect/rebuildtrees/rebuild.go index c1391eb..b1bbdb5 100644 --- a/cmd/btrfs-rec/inspect/rebuildtrees/rebuild.go +++ b/cmd/btrfs-rec/inspect/rebuildtrees/rebuild.go @@ -89,7 +89,7 @@ func NewRebuilder(ctx context.Context, fs *btrfs.FS, nodeList []btrfsvol.Logical scan: scanData, keyIO: keyIO, } - o.rebuilt = btrfsutil.NewRebuiltForrest(scanData.Superblock, scanData.Graph, keyIO, o) + o.rebuilt = btrfsutil.NewRebuiltForrest(scanData.Superblock, scanData.Graph, keyIO, forrestCallbacks{o}) return o, nil } @@ -286,7 +286,7 @@ func (o *rebuilder) processSettledItemQueue(ctx context.Context) error { ctx := dlog.WithField(ctx, "btrfs.inspect.rebuild-trees.rebuild.process.item", item.keyAndTree) o.curKey.TreeID = item.TreeID o.curKey.Key.Val = item.Key - btrfscheck.HandleItem(ctx, o, item.TreeID, btrfstree.Item{ + btrfscheck.HandleItem(ctx, graphCallbacks{o}, item.TreeID, btrfstree.Item{ Key: item.Key, Body: item.Body, }) diff --git a/cmd/btrfs-rec/inspect/rebuildtrees/rebuild_treecb.go b/cmd/btrfs-rec/inspect/rebuildtrees/rebuild_treecb.go index a422a47..c632e10 100644 --- a/cmd/btrfs-rec/inspect/rebuildtrees/rebuild_treecb.go +++ b/cmd/btrfs-rec/inspect/rebuildtrees/rebuild_treecb.go @@ -13,8 +13,12 @@ import ( "git.lukeshu.com/btrfs-progs-ng/lib/btrfs/btrfsvol" ) +type forrestCallbacks struct { + *rebuilder +} + // AddedItem implements btrfsutil.RebuiltForrestCallbacks. -func (o *rebuilder) AddedItem(_ context.Context, tree btrfsprim.ObjID, key btrfsprim.Key) { +func (o forrestCallbacks) AddedItem(_ context.Context, tree btrfsprim.ObjID, key btrfsprim.Key) { o.addedItemQueue.Insert(keyAndTree{ TreeID: tree, Key: key, @@ -22,14 +26,14 @@ func (o *rebuilder) AddedItem(_ context.Context, tree btrfsprim.ObjID, key btrfs } // AddedRoot implements btrfsutil.RebuiltForrestCallbacks. -func (o *rebuilder) AddedRoot(_ context.Context, tree btrfsprim.ObjID, _ btrfsvol.LogicalAddr) { +func (o forrestCallbacks) AddedRoot(_ context.Context, tree btrfsprim.ObjID, _ btrfsvol.LogicalAddr) { if retries := o.retryItemQueue[tree]; retries != nil { o.addedItemQueue.InsertFrom(retries) } } // LookupRoot implements btrfsutil.RebuiltForrestCallbacks. -func (o *rebuilder) LookupRoot(ctx context.Context, tree btrfsprim.ObjID) (offset btrfsprim.Generation, item btrfsitem.Root, ok bool) { +func (o forrestCallbacks) LookupRoot(ctx context.Context, tree btrfsprim.ObjID) (offset btrfsprim.Generation, item btrfsitem.Root, ok bool) { wantKey := WantWithTree{ TreeID: btrfsprim.ROOT_TREE_OBJECTID, Key: Want{ @@ -50,7 +54,7 @@ func (o *rebuilder) LookupRoot(ctx context.Context, tree btrfsprim.ObjID) (offse case *btrfsitem.Root: return btrfsprim.Generation(foundKey.Offset), *itemBody, true case *btrfsitem.Error: - o.FSErr(ctx, fmt.Errorf("error decoding item: %v: %w", foundKey, itemBody.Err)) + graphCallbacks(o).FSErr(ctx, fmt.Errorf("error decoding item: %v: %w", foundKey, itemBody.Err)) return 0, btrfsitem.Root{}, false default: // This is a panic because the item decoder should not emit ROOT_ITEM items as anything but @@ -60,7 +64,7 @@ func (o *rebuilder) LookupRoot(ctx context.Context, tree btrfsprim.ObjID) (offse } // LookupUUID implements btrfsutil.RebuiltForrestCallbacks. -func (o *rebuilder) LookupUUID(ctx context.Context, uuid btrfsprim.UUID) (id btrfsprim.ObjID, ok bool) { +func (o forrestCallbacks) LookupUUID(ctx context.Context, uuid btrfsprim.UUID) (id btrfsprim.ObjID, ok bool) { wantKey := WantWithTree{ TreeID: btrfsprim.UUID_TREE_OBJECTID, Key: wantFromKey(btrfsitem.UUIDToKey(uuid)), @@ -76,7 +80,7 @@ func (o *rebuilder) LookupUUID(ctx context.Context, uuid btrfsprim.UUID) (id btr case *btrfsitem.UUIDMap: return itemBody.ObjID, true case *btrfsitem.Error: - o.FSErr(ctx, fmt.Errorf("error decoding item: %v: %w", wantKey, itemBody.Err)) + graphCallbacks(o).FSErr(ctx, fmt.Errorf("error decoding item: %v: %w", wantKey, itemBody.Err)) return 0, false default: // This is a panic because the item decoder should not emit UUID_SUBVOL items as anything but diff --git a/cmd/btrfs-rec/inspect/rebuildtrees/rebuild_wantcb.go b/cmd/btrfs-rec/inspect/rebuildtrees/rebuild_wantcb.go index 78ed8ab..10fdcff 100644 --- a/cmd/btrfs-rec/inspect/rebuildtrees/rebuild_wantcb.go +++ b/cmd/btrfs-rec/inspect/rebuildtrees/rebuild_wantcb.go @@ -19,13 +19,17 @@ import ( "git.lukeshu.com/btrfs-progs-ng/lib/containers" ) +type graphCallbacks struct { + *rebuilder +} + // FSErr implements btrfscheck.GraphCallbacks. -func (*rebuilder) FSErr(ctx context.Context, e error) { +func (graphCallbacks) FSErr(ctx context.Context, e error) { dlog.Errorf(ctx, "filesystem error: %v", e) } // Want implements btrfscheck.GraphCallbacks. -func (o *rebuilder) Want(ctx context.Context, reason string, treeID btrfsprim.ObjID, objID btrfsprim.ObjID, typ btrfsprim.ItemType) { +func (o graphCallbacks) Want(ctx context.Context, reason string, treeID btrfsprim.ObjID, objID btrfsprim.ObjID, typ btrfsprim.ItemType) { wantKey := WantWithTree{ TreeID: treeID, Key: Want{ @@ -74,7 +78,7 @@ func (o *rebuilder) _want(ctx context.Context, wantKey WantWithTree) (key btrfsp } // WantOff implements btrfscheck.GraphCallbacks. -func (o *rebuilder) WantOff(ctx context.Context, reason string, treeID btrfsprim.ObjID, objID btrfsprim.ObjID, typ btrfsprim.ItemType, off uint64) { +func (o graphCallbacks) WantOff(ctx context.Context, reason string, treeID btrfsprim.ObjID, objID btrfsprim.ObjID, typ btrfsprim.ItemType, off uint64) { wantKey := WantWithTree{ TreeID: treeID, Key: Want{ @@ -118,7 +122,7 @@ func (o *rebuilder) _wantOff(ctx context.Context, wantKey WantWithTree) (ok bool } // WantDirIndex implements btrfscheck.GraphCallbacks. -func (o *rebuilder) WantDirIndex(ctx context.Context, reason string, treeID btrfsprim.ObjID, objID btrfsprim.ObjID, name []byte) { +func (o graphCallbacks) WantDirIndex(ctx context.Context, reason string, treeID btrfsprim.ObjID, objID btrfsprim.ObjID, name []byte) { wantKey := WantWithTree{ TreeID: treeID, Key: Want{ @@ -174,7 +178,7 @@ func (o *rebuilder) WantDirIndex(ctx context.Context, reason string, treeID btrf o.wantAugment(ctx, wantKey, wants) } -func (o *rebuilder) _walkRange( +func (o graphCallbacks) _walkRange( ctx context.Context, items *containers.SortedMap[btrfsprim.Key, btrfsutil.ItemPtr], treeID, objID btrfsprim.ObjID, typ btrfsprim.ItemType, @@ -239,7 +243,7 @@ func (a gap) Compare(b gap) int { return containers.NativeCompare(a.Beg, b.Beg) } -func (o *rebuilder) _wantRange( +func (o graphCallbacks) _wantRange( ctx context.Context, reason string, treeID btrfsprim.ObjID, objID btrfsprim.ObjID, typ btrfsprim.ItemType, beg, end uint64, @@ -353,7 +357,7 @@ func (o *rebuilder) _wantRange( // WantCSum implements btrfscheck.GraphCallbacks. // // interval is [beg, end) -func (o *rebuilder) WantCSum(ctx context.Context, reason string, inodeTree, inode btrfsprim.ObjID, beg, end btrfsvol.LogicalAddr) { +func (o graphCallbacks) WantCSum(ctx context.Context, reason string, inodeTree, inode btrfsprim.ObjID, beg, end btrfsvol.LogicalAddr) { inodeWant := WantWithTree{ TreeID: inodeTree, Key: Want{ @@ -392,7 +396,7 @@ func (o *rebuilder) WantCSum(ctx context.Context, reason string, inodeTree, inod } // WantFileExt implements btrfscheck.GraphCallbacks. -func (o *rebuilder) WantFileExt(ctx context.Context, reason string, treeID btrfsprim.ObjID, ino btrfsprim.ObjID, size int64) { +func (o graphCallbacks) WantFileExt(ctx context.Context, reason string, treeID btrfsprim.ObjID, ino btrfsprim.ObjID, size int64) { o._wantRange( ctx, reason, treeID, ino, btrfsprim.EXTENT_DATA_KEY, -- cgit v1.1-4-g5e80 From 1b7de33b1cc24f329efe63130858a5cd562d5378 Mon Sep 17 00:00:00 2001 From: Luke Shumaker Date: Wed, 1 Mar 2023 00:09:13 -0700 Subject: rebuildtrees: Be careful about what types are exported --- cmd/btrfs-rec/inspect/rebuildtrees/rebuild.go | 22 ++++++++++---------- .../inspect/rebuildtrees/rebuild_treecb.go | 6 +++--- .../inspect/rebuildtrees/rebuild_wantcb.go | 24 +++++++++++----------- .../inspect/rebuildtrees/rebuild_wanttyp.go | 22 ++++++++++---------- 4 files changed, 37 insertions(+), 37 deletions(-) diff --git a/cmd/btrfs-rec/inspect/rebuildtrees/rebuild.go b/cmd/btrfs-rec/inspect/rebuildtrees/rebuild.go index b1bbdb5..4937ee3 100644 --- a/cmd/btrfs-rec/inspect/rebuildtrees/rebuild.go +++ b/cmd/btrfs-rec/inspect/rebuildtrees/rebuild.go @@ -66,9 +66,9 @@ type rebuilder struct { } type treeAugmentQueue struct { - zero map[Want]struct{} - single map[Want]btrfsvol.LogicalAddr - multi map[Want]containers.Set[btrfsvol.LogicalAddr] + zero map[want]struct{} + single map[want]btrfsvol.LogicalAddr + multi map[want]containers.Set[btrfsvol.LogicalAddr] } type Rebuilder interface { @@ -208,7 +208,7 @@ func (o *rebuilder) processAddedItemQueue(ctx context.Context) error { } excPtr, ok := tree.PotentialItems(ctx).Load(key.Key) if ok && tree.ShouldReplace(incPtr.Node, excPtr.Node) { - wantKey := WantWithTree{ + wantKey := wantWithTree{ TreeID: key.TreeID, Key: wantFromKey(key.Key), } @@ -520,7 +520,7 @@ func (o *rebuilder) resolveTreeAugments(ctx context.Context, treeID btrfsprim.Ob //////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// -func (queue *treeAugmentQueue) has(wantKey Want) bool { +func (queue *treeAugmentQueue) has(wantKey want) bool { if queue != nil { if queue.zero != nil { if _, ok := queue.zero[wantKey]; ok { @@ -541,7 +541,7 @@ func (queue *treeAugmentQueue) has(wantKey Want) bool { return false } -func (queue *treeAugmentQueue) store(wantKey Want, choices containers.Set[btrfsvol.LogicalAddr]) { +func (queue *treeAugmentQueue) store(wantKey want, choices containers.Set[btrfsvol.LogicalAddr]) { if len(choices) == 0 && wantKey.OffsetType > offsetExact { // This wantKey is unlikely to come up again, so it's // not worth the RAM of storing a negative result. @@ -550,27 +550,27 @@ func (queue *treeAugmentQueue) store(wantKey Want, choices containers.Set[btrfsv switch len(choices) { case 0: if queue.zero == nil { - queue.zero = make(map[Want]struct{}) + queue.zero = make(map[want]struct{}) } queue.zero[wantKey] = struct{}{} case 1: if queue.single == nil { - queue.single = make(map[Want]btrfsvol.LogicalAddr) + queue.single = make(map[want]btrfsvol.LogicalAddr) } queue.single[wantKey] = choices.TakeOne() default: if queue.multi == nil { - queue.multi = make(map[Want]containers.Set[btrfsvol.LogicalAddr]) + queue.multi = make(map[want]containers.Set[btrfsvol.LogicalAddr]) } queue.multi[wantKey] = choices } } -func (o *rebuilder) hasAugment(wantKey WantWithTree) bool { +func (o *rebuilder) hasAugment(wantKey wantWithTree) bool { return o.augmentQueue[wantKey.TreeID].has(wantKey.Key) } -func (o *rebuilder) wantAugment(ctx context.Context, wantKey WantWithTree, choices containers.Set[btrfsvol.LogicalAddr]) { +func (o *rebuilder) wantAugment(ctx context.Context, wantKey wantWithTree, choices containers.Set[btrfsvol.LogicalAddr]) { if o.augmentQueue[wantKey.TreeID] == nil { o.augmentQueue[wantKey.TreeID] = new(treeAugmentQueue) } diff --git a/cmd/btrfs-rec/inspect/rebuildtrees/rebuild_treecb.go b/cmd/btrfs-rec/inspect/rebuildtrees/rebuild_treecb.go index c632e10..765ee76 100644 --- a/cmd/btrfs-rec/inspect/rebuildtrees/rebuild_treecb.go +++ b/cmd/btrfs-rec/inspect/rebuildtrees/rebuild_treecb.go @@ -34,9 +34,9 @@ func (o forrestCallbacks) AddedRoot(_ context.Context, tree btrfsprim.ObjID, _ b // LookupRoot implements btrfsutil.RebuiltForrestCallbacks. func (o forrestCallbacks) LookupRoot(ctx context.Context, tree btrfsprim.ObjID) (offset btrfsprim.Generation, item btrfsitem.Root, ok bool) { - wantKey := WantWithTree{ + wantKey := wantWithTree{ TreeID: btrfsprim.ROOT_TREE_OBJECTID, - Key: Want{ + Key: want{ ObjectID: tree, ItemType: btrfsitem.ROOT_ITEM_KEY, OffsetType: offsetAny, @@ -65,7 +65,7 @@ func (o forrestCallbacks) LookupRoot(ctx context.Context, tree btrfsprim.ObjID) // LookupUUID implements btrfsutil.RebuiltForrestCallbacks. func (o forrestCallbacks) LookupUUID(ctx context.Context, uuid btrfsprim.UUID) (id btrfsprim.ObjID, ok bool) { - wantKey := WantWithTree{ + wantKey := wantWithTree{ TreeID: btrfsprim.UUID_TREE_OBJECTID, Key: wantFromKey(btrfsitem.UUIDToKey(uuid)), } diff --git a/cmd/btrfs-rec/inspect/rebuildtrees/rebuild_wantcb.go b/cmd/btrfs-rec/inspect/rebuildtrees/rebuild_wantcb.go index 10fdcff..8bfdd06 100644 --- a/cmd/btrfs-rec/inspect/rebuildtrees/rebuild_wantcb.go +++ b/cmd/btrfs-rec/inspect/rebuildtrees/rebuild_wantcb.go @@ -30,9 +30,9 @@ func (graphCallbacks) FSErr(ctx context.Context, e error) { // Want implements btrfscheck.GraphCallbacks. func (o graphCallbacks) Want(ctx context.Context, reason string, treeID btrfsprim.ObjID, objID btrfsprim.ObjID, typ btrfsprim.ItemType) { - wantKey := WantWithTree{ + wantKey := wantWithTree{ TreeID: treeID, - Key: Want{ + Key: want{ ObjectID: objID, ItemType: typ, OffsetType: offsetAny, @@ -42,7 +42,7 @@ func (o graphCallbacks) Want(ctx context.Context, reason string, treeID btrfspri o._want(ctx, wantKey) } -func (o *rebuilder) _want(ctx context.Context, wantKey WantWithTree) (key btrfsprim.Key, ok bool) { +func (o *rebuilder) _want(ctx context.Context, wantKey wantWithTree) (key btrfsprim.Key, ok bool) { if o.rebuilt.Tree(ctx, wantKey.TreeID) == nil { o.enqueueRetry(wantKey.TreeID) return btrfsprim.Key{}, false @@ -79,9 +79,9 @@ func (o *rebuilder) _want(ctx context.Context, wantKey WantWithTree) (key btrfsp // WantOff implements btrfscheck.GraphCallbacks. func (o graphCallbacks) WantOff(ctx context.Context, reason string, treeID btrfsprim.ObjID, objID btrfsprim.ObjID, typ btrfsprim.ItemType, off uint64) { - wantKey := WantWithTree{ + wantKey := wantWithTree{ TreeID: treeID, - Key: Want{ + Key: want{ ObjectID: objID, ItemType: typ, OffsetType: offsetExact, @@ -92,7 +92,7 @@ func (o graphCallbacks) WantOff(ctx context.Context, reason string, treeID btrfs o._wantOff(ctx, wantKey) } -func (o *rebuilder) _wantOff(ctx context.Context, wantKey WantWithTree) (ok bool) { +func (o *rebuilder) _wantOff(ctx context.Context, wantKey wantWithTree) (ok bool) { if o.rebuilt.Tree(ctx, wantKey.TreeID) == nil { o.enqueueRetry(wantKey.TreeID) return false @@ -123,9 +123,9 @@ func (o *rebuilder) _wantOff(ctx context.Context, wantKey WantWithTree) (ok bool // WantDirIndex implements btrfscheck.GraphCallbacks. func (o graphCallbacks) WantDirIndex(ctx context.Context, reason string, treeID btrfsprim.ObjID, objID btrfsprim.ObjID, name []byte) { - wantKey := WantWithTree{ + wantKey := wantWithTree{ TreeID: treeID, - Key: Want{ + Key: want{ ObjectID: objID, ItemType: btrfsitem.DIR_INDEX_KEY, OffsetType: offsetName, @@ -248,9 +248,9 @@ func (o graphCallbacks) _wantRange( treeID btrfsprim.ObjID, objID btrfsprim.ObjID, typ btrfsprim.ItemType, beg, end uint64, ) { - wantKey := WantWithTree{ + wantKey := wantWithTree{ TreeID: treeID, - Key: Want{ + Key: want{ ObjectID: objID, ItemType: typ, OffsetType: offsetAny, @@ -358,9 +358,9 @@ func (o graphCallbacks) _wantRange( // // interval is [beg, end) func (o graphCallbacks) WantCSum(ctx context.Context, reason string, inodeTree, inode btrfsprim.ObjID, beg, end btrfsvol.LogicalAddr) { - inodeWant := WantWithTree{ + inodeWant := wantWithTree{ TreeID: inodeTree, - Key: Want{ + Key: want{ ObjectID: inode, ItemType: btrfsitem.INODE_ITEM_KEY, OffsetType: offsetExact, diff --git a/cmd/btrfs-rec/inspect/rebuildtrees/rebuild_wanttyp.go b/cmd/btrfs-rec/inspect/rebuildtrees/rebuild_wanttyp.go index 8fe8a49..6c9d72b 100644 --- a/cmd/btrfs-rec/inspect/rebuildtrees/rebuild_wanttyp.go +++ b/cmd/btrfs-rec/inspect/rebuildtrees/rebuild_wanttyp.go @@ -23,8 +23,8 @@ const ( offsetName ) -type Want struct { - // TODO(lukeshu): Delete the 'Want' type in favor of +type want struct { + // TODO(lukeshu): Delete the 'want' type in favor of // btrfstree.Search. ObjectID btrfsprim.ObjID ItemType btrfsprim.ItemType @@ -34,7 +34,7 @@ type Want struct { OffsetName string } -func (a Want) Compare(b Want) int { +func (a want) Compare(b want) int { if d := containers.NativeCompare(a.ObjectID, b.ObjectID); d != 0 { return d } @@ -56,7 +56,7 @@ func (a Want) Compare(b Want) int { return 0 } -func (o Want) Key() btrfsprim.Key { +func (o want) Key() btrfsprim.Key { return btrfsprim.Key{ ObjectID: o.ObjectID, ItemType: o.ItemType, @@ -64,8 +64,8 @@ func (o Want) Key() btrfsprim.Key { } } -func wantFromKey(k btrfsprim.Key) Want { - return Want{ +func wantFromKey(k btrfsprim.Key) want { + return want{ ObjectID: k.ObjectID, ItemType: k.ItemType, OffsetType: offsetExact, @@ -73,7 +73,7 @@ func wantFromKey(k btrfsprim.Key) Want { } } -func (o Want) String() string { +func (o want) String() string { switch o.OffsetType { case offsetAny: return fmt.Sprintf("{%v %v ?}", o.ObjectID, o.ItemType) @@ -88,12 +88,12 @@ func (o Want) String() string { } } -type WantWithTree struct { +type wantWithTree struct { TreeID btrfsprim.ObjID - Key Want + Key want } -func (o WantWithTree) String() string { +func (o wantWithTree) String() string { return fmt.Sprintf("tree=%v key=%v", o.TreeID, o.Key) } @@ -102,7 +102,7 @@ const ( logFieldTreeWant = "btrfs.util.rebuilt-forrest.add-tree.want" ) -func withWant(ctx context.Context, logField, reason string, wantKey WantWithTree) context.Context { +func withWant(ctx context.Context, logField, reason string, wantKey wantWithTree) context.Context { ctx = dlog.WithField(ctx, logField+".reason", reason) ctx = dlog.WithField(ctx, logField+".key", wantKey) return ctx -- cgit v1.1-4-g5e80 From 5ae8f865cdd8607f29fa37267dad2b436e9c9103 Mon Sep 17 00:00:00 2001 From: Luke Shumaker Date: Fri, 3 Mar 2023 10:25:01 -0700 Subject: btrfsinspect: PrintLogicalSpace and PrintPhysicalSpace are unused --- lib/btrfsutil/print_addrspace.go | 73 ---------------------------------------- 1 file changed, 73 deletions(-) delete mode 100644 lib/btrfsutil/print_addrspace.go 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 -// -// 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)) -} -- cgit v1.1-4-g5e80 From 17e5d1366a77bbe0e8d32b7bf16829a4f855e854 Mon Sep 17 00:00:00 2001 From: Luke Shumaker Date: Fri, 10 Mar 2023 15:22:07 -0700 Subject: tree-wide: s/TreePath/Path/g btrfstree.TreePath stutters. --- cmd/btrfs-rec/inspect/dumptrees/print_tree.go | 8 +++---- cmd/btrfs-rec/inspect_lstrees.go | 6 ++--- cmd/btrfs-rec/inspect_spewitems.go | 4 ++-- lib/btrfs/btrfstree/btree.go | 20 ++++++++--------- lib/btrfs/btrfstree/btree_tree.go | 32 +++++++++++++-------------- lib/btrfs/btrfstree/path.go | 22 +++++++++--------- lib/btrfs/btrfstree/readnode.go | 2 +- lib/btrfs/io2_lv.go | 2 +- lib/btrfs/io3_btree.go | 4 ++-- lib/btrfsutil/old_rebuilt_forrest.go | 10 ++++----- lib/btrfsutil/rebuilt_forrest.go | 2 +- lib/btrfsutil/walk.go | 4 ++-- 12 files changed, 58 insertions(+), 58 deletions(-) diff --git a/cmd/btrfs-rec/inspect/dumptrees/print_tree.go b/cmd/btrfs-rec/inspect/dumptrees/print_tree.go index 9572f3a..60303e9 100644 --- a/cmd/btrfs-rec/inspect/dumptrees/print_tree.go +++ b/cmd/btrfs-rec/inspect/dumptrees/print_tree.go @@ -53,7 +53,7 @@ func DumpTrees(ctx context.Context, out io.Writer, fs *btrfs.FS) { dlog.Error(ctx, err) }, btrfstree.TreeWalkHandler{ - Item: func(_ btrfstree.TreePath, item btrfstree.Item) error { + Item: func(_ btrfstree.Path, item btrfstree.Item) error { if item.Key.ItemType != btrfsitem.ROOT_ITEM_KEY { return nil } @@ -99,12 +99,12 @@ 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.TreePath, node *btrfstree.Node) error { + Node: func(path btrfstree.Path, node *btrfstree.Node) error { printHeaderInfo(out, node) itemOffset = node.Size - uint32(nodeHeaderSize) return nil }, - PreKeyPointer: func(path btrfstree.TreePath, item btrfstree.KeyPointer) error { + PreKeyPointer: func(path btrfstree.Path, item btrfstree.KeyPointer) error { treeID := path[0].FromTree textui.Fprintf(out, "\tkey %v block %v gen %v\n", item.Key.Format(treeID), @@ -112,7 +112,7 @@ func printTree(ctx context.Context, out io.Writer, fs *btrfs.FS, treeID btrfspri item.Generation) return nil }, - Item: func(path btrfstree.TreePath, item btrfstree.Item) error { + Item: func(path btrfstree.Path, item btrfstree.Item) error { treeID := path[0].FromTree i := path.Node(-1).FromItemSlot bs, _ := binstruct.Marshal(item.Body) diff --git a/cmd/btrfs-rec/inspect_lstrees.go b/cmd/btrfs-rec/inspect_lstrees.go index 70f4f51..1541012 100644 --- a/cmd/btrfs-rec/inspect_lstrees.go +++ b/cmd/btrfs-rec/inspect_lstrees.go @@ -75,16 +75,16 @@ func init() { treeErrCnt++ }, TreeWalkHandler: btrfstree.TreeWalkHandler{ - Node: func(path btrfstree.TreePath, node *btrfstree.Node) error { + Node: func(path btrfstree.Path, node *btrfstree.Node) error { visitedNodes.Insert(path.Node(-1).ToNodeAddr) return nil }, - Item: func(_ btrfstree.TreePath, item btrfstree.Item) error { + Item: func(_ btrfstree.Path, item btrfstree.Item) error { typ := item.Key.ItemType treeItemCnt[typ]++ return nil }, - BadItem: func(_ btrfstree.TreePath, item btrfstree.Item) error { + BadItem: func(_ btrfstree.Path, item btrfstree.Item) error { typ := item.Key.ItemType treeItemCnt[typ]++ return nil diff --git a/cmd/btrfs-rec/inspect_spewitems.go b/cmd/btrfs-rec/inspect_spewitems.go index d8a65ae..b83e989 100644 --- a/cmd/btrfs-rec/inspect_spewitems.go +++ b/cmd/btrfs-rec/inspect_spewitems.go @@ -34,13 +34,13 @@ func init() { dlog.Error(ctx, err) }, TreeWalkHandler: btrfstree.TreeWalkHandler{ - Item: func(path btrfstree.TreePath, item btrfstree.Item) error { + Item: func(path btrfstree.Path, item btrfstree.Item) error { textui.Fprintf(os.Stdout, "%s = ", path) spew.Dump(item) _, _ = os.Stdout.WriteString("\n") return nil }, - BadItem: func(path btrfstree.TreePath, item btrfstree.Item) error { + BadItem: func(path btrfstree.Path, item btrfstree.Item) error { textui.Fprintf(os.Stdout, "%s = ", path) spew.Dump(item) _, _ = os.Stdout.WriteString("\n") diff --git a/lib/btrfs/btrfstree/btree.go b/lib/btrfs/btrfstree/btree.go index c71aad5..e91fcc1 100644 --- a/lib/btrfs/btrfstree/btree.go +++ b/lib/btrfs/btrfstree/btree.go @@ -69,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, *Node) error - BadNode func(TreePath, *Node, error) error - PostNode func(TreePath, *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 } @@ -94,5 +94,5 @@ func (e *TreeError) Error() string { type NodeSource interface { Superblock() (*Superblock, error) - ReadNode(TreePath) (*Node, error) + ReadNode(Path) (*Node, error) } diff --git a/lib/btrfs/btrfstree/btree_tree.go b/lib/btrfs/btrfstree/btree_tree.go index 7561314..459f481 100644 --- a/lib/btrfs/btrfstree/btree_tree.go +++ b/lib/btrfs/btrfstree/btree_tree.go @@ -26,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) @@ -39,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, @@ -50,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 } @@ -100,7 +100,7 @@ func (fs TreeOperatorImpl) treeWalk(ctx context.Context, path TreePath, errHandl if i+1 < len(node.BodyInterior) { toMaxKey = node.BodyInterior[i+1].Key.Mm() } - itemPath := append(path, TreePathElem{ + itemPath := append(path, PathElem{ FromTree: node.Head.Owner, FromItemSlot: i, ToNodeAddr: item.BlockPtr, @@ -128,7 +128,7 @@ func (fs TreeOperatorImpl) treeWalk(ctx context.Context, path TreePath, errHandl } } for i, item := range node.BodyLeaf { - itemPath := append(path, TreePathElem{ + itemPath := append(path, PathElem{ FromTree: node.Head.Owner, FromItemSlot: i, ToKey: item.Key, @@ -167,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, *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, @@ -209,7 +209,7 @@ func (fs TreeOperatorImpl) treeSearch(treeRoot TreeRoot, fn func(btrfsprim.Key, if lastGood+1 < len(node.BodyInterior) { toMaxKey = node.BodyInterior[lastGood+1].Key.Mm() } - path = append(path, TreePathElem{ + path = append(path, PathElem{ FromTree: node.Head.Owner, FromItemSlot: lastGood, ToNodeAddr: node.BodyInterior[lastGood].BlockPtr, @@ -239,7 +239,7 @@ func (fs TreeOperatorImpl) treeSearch(treeRoot TreeRoot, fn func(btrfsprim.Key, node.Free() return nil, nil, ErrNoItem } - path = append(path, TreePathElem{ + path = append(path, PathElem{ FromTree: node.Head.Owner, FromItemSlot: slot, ToKey: node.BodyLeaf[slot].Key, @@ -250,7 +250,7 @@ func (fs TreeOperatorImpl) treeSearch(treeRoot TreeRoot, fn func(btrfsprim.Key, } } -func (fs TreeOperatorImpl) prev(path TreePath, node *Node) (TreePath, *Node, error) { +func (fs TreeOperatorImpl) prev(path Path, node *Node) (Path, *Node, error) { var err error path = path.DeepCopy() @@ -285,7 +285,7 @@ func (fs TreeOperatorImpl) prev(path TreePath, node *Node) (TreePath, *Node, err } } if node.Head.Level > 0 { - path = append(path, TreePathElem{ + path = append(path, PathElem{ FromTree: node.Head.Owner, FromItemSlot: len(node.BodyInterior) - 1, ToNodeAddr: node.BodyInterior[len(node.BodyInterior)-1].BlockPtr, @@ -295,7 +295,7 @@ func (fs TreeOperatorImpl) prev(path TreePath, node *Node) (TreePath, *Node, err ToMaxKey: path.Node(-1).ToMaxKey, }) } else { - path = append(path, TreePathElem{ + path = append(path, PathElem{ FromTree: node.Head.Owner, FromItemSlot: len(node.BodyLeaf) - 1, ToKey: node.BodyLeaf[len(node.BodyLeaf)-1].Key, @@ -315,7 +315,7 @@ func (fs TreeOperatorImpl) prev(path TreePath, node *Node) (TreePath, *Node, err return path, node, nil } -func (fs TreeOperatorImpl) next(path TreePath, node *Node) (TreePath, *Node, error) { +func (fs TreeOperatorImpl) next(path Path, node *Node) (Path, *Node, error) { var err error path = path.DeepCopy() @@ -373,7 +373,7 @@ func (fs TreeOperatorImpl) next(path TreePath, node *Node) (TreePath, *Node, err if len(node.BodyInterior) > 1 { toMaxKey = node.BodyInterior[1].Key.Mm() } - path = append(path, TreePathElem{ + path = append(path, PathElem{ FromTree: node.Head.Owner, FromItemSlot: 0, ToNodeAddr: node.BodyInterior[0].BlockPtr, @@ -383,7 +383,7 @@ func (fs TreeOperatorImpl) next(path TreePath, node *Node) (TreePath, *Node, err ToMaxKey: toMaxKey, }) } else { - path = append(path, TreePathElem{ + path = append(path, PathElem{ FromTree: node.Head.Owner, FromItemSlot: 0, ToKey: node.BodyInterior[0].Key, 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 1c242ac..c5d9145 100644 --- a/lib/btrfs/btrfstree/readnode.go +++ b/lib/btrfs/btrfstree/readnode.go @@ -33,7 +33,7 @@ type NodeFile interface { // 'NodeSource' interface. func FSReadNode( fs NodeFile, - path TreePath, + path Path, ) (*Node, error) { sb, err := fs.Superblock() if err != 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 467bbde..80ab10f 100644 --- a/lib/btrfs/io3_btree.go +++ b/lib/btrfs/io3_btree.go @@ -17,7 +17,7 @@ import ( // btrfstree.NodeSource //////////////////////////////////////////////////////// // ReadNode implements btrfstree.NodeSource. -func (fs *FS) ReadNode(path btrfstree.TreePath) (*btrfstree.Node, error) { +func (fs *FS) ReadNode(path btrfstree.Path) (*btrfstree.Node, error) { return btrfstree.FSReadNode(fs, path) } @@ -37,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/btrfsutil/old_rebuilt_forrest.go b/lib/btrfsutil/old_rebuilt_forrest.go index 8bc02df..5f6c718 100644 --- a/lib/btrfsutil/old_rebuilt_forrest.go +++ b/lib/btrfsutil/old_rebuilt_forrest.go @@ -178,7 +178,7 @@ func (bt *OldRebuiltForrest) rawTreeWalk(root btrfstree.TreeRoot, cacheEntry old var curNode nodeInfo cbs := btrfstree.TreeWalkHandler{ - BadNode: func(path btrfstree.TreePath, node *btrfstree.Node, err error) error { + BadNode: func(path btrfstree.Path, node *btrfstree.Node, err error) error { if node != nil { curNode = nodeInfo{ LAddr: path.Node(-1).ToNodeAddr, @@ -191,7 +191,7 @@ func (bt *OldRebuiltForrest) rawTreeWalk(root btrfstree.TreeRoot, cacheEntry old } return err }, - Node: func(path btrfstree.TreePath, node *btrfstree.Node) error { + Node: func(path btrfstree.Path, node *btrfstree.Node) error { curNode = nodeInfo{ LAddr: path.Node(-1).ToNodeAddr, Level: node.Head.Level, @@ -202,7 +202,7 @@ func (bt *OldRebuiltForrest) rawTreeWalk(root btrfstree.TreeRoot, cacheEntry old } return nil }, - Item: func(path btrfstree.TreePath, item btrfstree.Item) error { + 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 @@ -340,7 +340,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, }}, @@ -365,7 +365,7 @@ func (bt *OldRebuiltForrest) TreeWalk(ctx context.Context, treeID btrfsprim.ObjI } item := node.BodyLeaf[indexItem.Value.Slot] - itemPath := btrfstree.TreePath{ + itemPath := btrfstree.Path{ { FromTree: treeID, ToNodeAddr: indexItem.Value.Node.LAddr, diff --git a/lib/btrfsutil/rebuilt_forrest.go b/lib/btrfsutil/rebuilt_forrest.go index 70ece13..0e8f5ad 100644 --- a/lib/btrfsutil/rebuilt_forrest.go +++ b/lib/btrfsutil/rebuilt_forrest.go @@ -40,7 +40,7 @@ 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 // 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 +// Copyright (C) 2022-2023 Luke Shumaker // // 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 -- cgit v1.1-4-g5e80 From ceb9041cc7c838b3833ebc20cd97b02fbd3c92b3 Mon Sep 17 00:00:00 2001 From: Luke Shumaker Date: Thu, 2 Mar 2023 20:43:48 -0700 Subject: btrfsutil: OldRebuildForrest: Drop the Augment method --- lib/btrfsutil/old_rebuilt_forrest.go | 31 ++----------------------------- 1 file changed, 2 insertions(+), 29 deletions(-) diff --git a/lib/btrfsutil/old_rebuilt_forrest.go b/lib/btrfsutil/old_rebuilt_forrest.go index 5f6c718..f59a1f9 100644 --- a/lib/btrfsutil/old_rebuilt_forrest.go +++ b/lib/btrfsutil/old_rebuilt_forrest.go @@ -148,7 +148,7 @@ func (bt *OldRebuiltForrest) RebuiltTree(treeID btrfsprim.ObjID) oldRebuiltTree cacheEntry.RootErr = err } else { dlog.Infof(bt.ctx, "indexing tree %v...", treeID) - bt.rawTreeWalk(*treeRoot, cacheEntry, nil) + bt.rawTreeWalk(*treeRoot, cacheEntry) dlog.Infof(bt.ctx, "... done indexing tree %v", treeID) } @@ -162,7 +162,7 @@ func (bt *OldRebuiltForrest) RebuiltTree(treeID btrfsprim.ObjID) oldRebuiltTree func discardOK[T any](x T, _ bool) T { return x } -func (bt *OldRebuiltForrest) rawTreeWalk(root btrfstree.TreeRoot, cacheEntry oldRebuiltTree, walked *[]btrfsprim.Key) { +func (bt *OldRebuiltForrest) rawTreeWalk(root btrfstree.TreeRoot, cacheEntry oldRebuiltTree) { 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 @@ -216,9 +216,6 @@ func (bt *OldRebuiltForrest) rawTreeWalk(root btrfstree.TreeRoot, cacheEntry old Node: curNode, Slot: path.Node(-1).FromItemSlot, }) - if walked != nil { - *walked = append(*walked, item.Key) - } return nil }, } @@ -396,27 +393,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 - } - node, err := btrfstree.ReadNode[btrfsvol.LogicalAddr](bt.inner, *sb, nodeAddr, btrfstree.NodeExpectations{}) - defer node.Free() - if err != nil { - return nil, err - } - var ret []btrfsprim.Key - bt.rawTreeWalk(btrfstree.TreeRoot{ - TreeID: treeID, - RootNode: nodeAddr, - Level: node.Head.Level, - Generation: node.Head.Generation, - }, tree, &ret) - return ret, nil -} -- cgit v1.1-4-g5e80 From 26e58f1cd1d47b63b1b05b26c73c4f69f7e245cb Mon Sep 17 00:00:00 2001 From: Luke Shumaker Date: Mon, 13 Mar 2023 18:52:51 -0600 Subject: btrfsutil: OldRebuiltForrest: Hoist logic from .RebuiltTree to .rawTreeWalk It's OK that for ROOT_TREE_OBJECTID it now calls btrfstree.LookupTreeRoot on `bt` instead of `bt.inner`, because LookupTreeRoot doesn't actually use that argument for ROOT_TREE_OBJECTID. --- lib/btrfsutil/old_rebuilt_forrest.go | 36 ++++++++++++++++-------------------- 1 file changed, 16 insertions(+), 20 deletions(-) diff --git a/lib/btrfsutil/old_rebuilt_forrest.go b/lib/btrfsutil/old_rebuilt_forrest.go index f59a1f9..c146935 100644 --- a/lib/btrfsutil/old_rebuilt_forrest.go +++ b/lib/btrfsutil/old_rebuilt_forrest.go @@ -115,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() @@ -137,20 +130,12 @@ 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) - } } cacheEntry := newOldRebuiltTree() - if err != nil { - cacheEntry.RootErr = err - } else { - dlog.Infof(bt.ctx, "indexing tree %v...", treeID) - bt.rawTreeWalk(*treeRoot, cacheEntry) - dlog.Infof(bt.ctx, "... done indexing tree %v", treeID) - } + 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 @@ -162,7 +147,18 @@ func (bt *OldRebuiltForrest) RebuiltTree(treeID btrfsprim.ObjID) oldRebuiltTree func discardOK[T any](x T, _ bool) T { return x } -func (bt *OldRebuiltForrest) rawTreeWalk(root btrfstree.TreeRoot, cacheEntry oldRebuiltTree) { +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 @@ -220,7 +216,7 @@ func (bt *OldRebuiltForrest) rawTreeWalk(root btrfstree.TreeRoot, cacheEntry old }, } - 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) { -- cgit v1.1-4-g5e80 From e1569565240cf6487ebeb5ec4c1386c8ba70f493 Mon Sep 17 00:00:00 2001 From: Luke Shumaker Date: Thu, 2 Mar 2023 22:35:00 -0700 Subject: btrfs: io4_fs.go: Subvolume: Don't have public members; use a constructor --- cmd/btrfs-rec/inspect/mount/mount.go | 35 +++++++++------- cmd/btrfs-rec/inspect_lsfiles.go | 14 +++---- lib/btrfs/io4_fs.go | 80 ++++++++++++++++++++---------------- 3 files changed, 71 insertions(+), 58 deletions(-) diff --git a/cmd/btrfs-rec/inspect/mount/mount.go b/cmd/btrfs-rec/inspect/mount/mount.go index 0e8faf1..4049393 100644 --- a/cmd/btrfs-rec/inspect/mount/mount.go +++ b/cmd/btrfs-rec/inspect/mount/mount.go @@ -28,6 +28,7 @@ import ( "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/btrfsutil" "git.lukeshu.com/btrfs-progs-ng/lib/containers" "git.lukeshu.com/btrfs-progs-ng/lib/maps" @@ -45,14 +46,21 @@ func MountRO(ctx context.Context, fs *btrfs.FS, mountpoint string, noChecksums b deviceName = abs } + sb, err := fs.Superblock() + if err != nil { + return err + } + rootSubvol := &subvolume{ - Subvolume: btrfs.Subvolume{ - FS: btrfsutil.NewOldRebuiltForrest(ctx, fs), - TreeID: btrfsprim.FS_TREE_OBJECTID, - NoChecksums: noChecksums, - }, + Subvolume: btrfs.NewSubvolume( + btrfsutil.NewOldRebuiltForrest(ctx, fs), + btrfsprim.FS_TREE_OBJECTID, + noChecksums, + ), DeviceName: deviceName, Mountpoint: mountpoint, + + sb: sb, } return rootSubvol.Run(ctx) } @@ -107,10 +115,12 @@ type fileState struct { } type subvolume struct { - btrfs.Subvolume + *btrfs.Subvolume DeviceName string Mountpoint string + sb *btrfstree.Superblock + fuseutil.NotImplementedFileSystem lastHandle uint64 dirHandles typedsync.Map[fuseops.HandleID, *dirState] @@ -189,11 +199,8 @@ func (sv *subvolume) LoadDir(inode btrfsprim.ObjID) (val *btrfs.Dir, err error) workerName := fmt.Sprintf("%d-%s", val.Inode, filepath.Base(subMountpoint)) sv.grp.Go(workerName, func(ctx context.Context) error { subSv := &subvolume{ - Subvolume: btrfs.Subvolume{ - FS: sv.FS, - TreeID: entry.Location.ObjectID, - NoChecksums: sv.NoChecksums, - }, + sb: sv.sb, + Subvolume: sv.NewChildSubvolume(entry.Location.ObjectID), DeviceName: sv.DeviceName, Mountpoint: filepath.Join(sv.Mountpoint, subMountpoint[1:]), } @@ -208,11 +215,9 @@ func (sv *subvolume) LoadDir(inode btrfsprim.ObjID) (val *btrfs.Dir, err error) } func (sv *subvolume) StatFS(_ context.Context, op *fuseops.StatFSOp) error { + sb := sv.sb + // See linux.git/fs/btrfs/super.c:btrfs_statfs() - sb, err := sv.FS.Superblock() - if err != nil { - return err - } op.IoSize = sb.SectorSize op.BlockSize = sb.SectorSize diff --git a/cmd/btrfs-rec/inspect_lsfiles.go b/cmd/btrfs-rec/inspect_lsfiles.go index a2b46ab..e9fd057 100644 --- a/cmd/btrfs-rec/inspect_lsfiles.go +++ b/cmd/btrfs-rec/inspect_lsfiles.go @@ -45,10 +45,11 @@ func init() { }() ctx := cmd.Context() - printSubvol(out, "", true, "/", &btrfs.Subvolume{ - FS: btrfsutil.NewOldRebuiltForrest(ctx, fs), - TreeID: btrfsprim.FS_TREE_OBJECTID, - }) + printSubvol(out, "", true, "/", btrfs.NewSubvolume( + btrfsutil.NewOldRebuiltForrest(ctx, fs), + btrfsprim.FS_TREE_OBJECTID, + false, + )) return nil }), @@ -160,10 +161,7 @@ func printDirEntry(out io.Writer, prefix string, isLast bool, subvol *btrfs.Subv } printDir(out, prefix, isLast, name, dir) case btrfsitem.ROOT_ITEM_KEY: - printSubvol(out, prefix, isLast, name, &btrfs.Subvolume{ - FS: subvol.FS, - TreeID: entry.Location.ObjectID, - }) + printSubvol(out, prefix, isLast, name, subvol.NewChildSubvolume(entry.Location.ObjectID)) default: panic(fmt.Errorf("TODO: I don't know how to handle an FT_DIR with location.ItemType=%v: %q", entry.Location.ItemType, name)) diff --git a/lib/btrfs/io4_fs.go b/lib/btrfs/io4_fs.go index e4511a5..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" @@ -63,15 +62,13 @@ type File struct { } type Subvolume struct { - FS interface { + fs interface { btrfstree.TreeOperator Superblock() (*btrfstree.Superblock, error) diskio.ReaderAt[btrfsvol.LogicalAddr] } TreeID btrfsprim.ObjID - NoChecksums bool - - initOnce sync.Once + noChecksums bool rootVal btrfsitem.Root rootErr error @@ -82,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, @@ -145,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{ @@ -153,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 { @@ -200,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) @@ -337,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) @@ -449,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 } @@ -458,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 { @@ -467,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) } -- cgit v1.1-4-g5e80 From cd199b402673b154add1e492b8ddfec43309dc5d Mon Sep 17 00:00:00 2001 From: Luke Shumaker Date: Fri, 3 Mar 2023 09:56:06 -0700 Subject: cmd/btrfs-rec: inspect ls-files: Move the code to a sub-package --- cmd/btrfs-rec/inspect/lsfiles/lsfiles.go | 249 +++++++++++++++++++++++++++++++ cmd/btrfs-rec/inspect_lsfiles.go | 226 +--------------------------- 2 files changed, 253 insertions(+), 222 deletions(-) create mode 100644 cmd/btrfs-rec/inspect/lsfiles/lsfiles.go diff --git a/cmd/btrfs-rec/inspect/lsfiles/lsfiles.go b/cmd/btrfs-rec/inspect/lsfiles/lsfiles.go new file mode 100644 index 0000000..a713b8a --- /dev/null +++ b/cmd/btrfs-rec/inspect/lsfiles/lsfiles.go @@ -0,0 +1,249 @@ +// Copyright (C) 2022-2023 Luke Shumaker +// +// SPDX-License-Identifier: GPL-2.0-or-later + +// Package lsfiles is the guts of the `btrfs-rec inspect ls-files` +// command, which prints a tree-listing of all files in the +// filesystem. +package lsfiles + +import ( + "errors" + "fmt" + "io" + "path" + "strings" + + "github.com/datawire/dlib/derror" + + "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" + "git.lukeshu.com/btrfs-progs-ng/lib/diskio" + "git.lukeshu.com/btrfs-progs-ng/lib/maps" + "git.lukeshu.com/btrfs-progs-ng/lib/textui" +) + +func LsFiles( + out io.Writer, + fs interface { + btrfstree.TreeOperator + Superblock() (*btrfstree.Superblock, error) + diskio.ReaderAt[btrfsvol.LogicalAddr] + }, +) (err error) { + defer func() { + if _err := derror.PanicToError(recover()); _err != nil { + textui.Fprintf(out, "\n\n%+v\n", _err) + err = _err + } + }() + + printSubvol(out, "", true, "/", btrfs.NewSubvolume( + fs, + btrfsprim.FS_TREE_OBJECTID, + false, + )) + + return nil +} + +const ( + tS = "    " + tl = "│   " + tT = "├── " + tL = "└── " +) + +func printText(out io.Writer, prefix string, isLast bool, name, text string) { + first, rest := tT, tl + if isLast { + first, rest = tL, tS + } + for i, line := range strings.Split(textui.Sprintf("%q %s", name, text), "\n") { + _, _ = io.WriteString(out, prefix) + if i == 0 { + _, _ = io.WriteString(out, first) + } else { + _, _ = io.WriteString(out, rest) + } + _, _ = io.WriteString(out, line) + _, _ = io.WriteString(out, "\n") + } +} + +func printSubvol(out io.Writer, prefix string, isLast bool, name string, subvol *btrfs.Subvolume) { + rootInode, err := subvol.GetRootInode() + if err != nil { + printText(out, prefix, isLast, name+"/", textui.Sprintf("subvol_id=%v err=%v", + subvol.TreeID, fmtErr(err))) + return + } + dir, err := subvol.LoadDir(rootInode) + if err != nil { + printText(out, prefix, isLast, name+"/", textui.Sprintf("subvol_id=%v err=%v", + subvol.TreeID, fmtErr(err))) + return + } + if name == "/" { + printDir(out, prefix, isLast, name, dir) + return + } + printText(out, prefix, isLast, name+"/", textui.Sprintf("subvol_id=%v", subvol.TreeID)) + if isLast { + prefix += tS + } else { + prefix += tl + } + printDir(out, prefix, true, name, dir) +} + +func fmtErr(err error) string { + errStr := err.Error() + if strings.Contains(errStr, "\n") { + errStr = "\\\n" + errStr + } + return errStr +} + +func fmtInode(inode btrfs.BareInode) string { + var mode btrfsitem.StatMode + if inode.InodeItem == nil { + inode.Errs = append(inode.Errs, errors.New("missing INODE_ITEM")) + } else { + mode = inode.InodeItem.Mode + } + ret := textui.Sprintf("ino=%v mode=%v", inode.Inode, mode) + if len(inode.Errs) > 0 { + ret += " err=" + fmtErr(inode.Errs) + } + return ret +} + +func printDir(out io.Writer, prefix string, isLast bool, name string, dir *btrfs.Dir) { + printText(out, prefix, isLast, name+"/", fmtInode(dir.BareInode)) + if isLast { + prefix += tS + } else { + prefix += tl + } + for i, childName := range maps.SortedKeys(dir.ChildrenByName) { + printDirEntry( + out, + prefix, + i == len(dir.ChildrenByName)-1, + dir.SV, + path.Join(name, childName), + dir.ChildrenByName[childName]) + } +} + +func printDirEntry(out io.Writer, prefix string, isLast bool, subvol *btrfs.Subvolume, name string, entry btrfsitem.DirEntry) { + if len(entry.Data) != 0 { + panic(fmt.Errorf("TODO: I don't know how to handle dirent.data: %q", name)) + } + switch entry.Type { + case btrfsitem.FT_DIR: + switch entry.Location.ItemType { + case btrfsitem.INODE_ITEM_KEY: + dir, err := subvol.LoadDir(entry.Location.ObjectID) + if err != nil { + printText(out, prefix, isLast, name, textui.Sprintf("%v err=%v", entry.Type, fmtErr(err))) + return + } + printDir(out, prefix, isLast, name, dir) + case btrfsitem.ROOT_ITEM_KEY: + printSubvol(out, prefix, isLast, name, subvol.NewChildSubvolume(entry.Location.ObjectID)) + default: + panic(fmt.Errorf("TODO: I don't know how to handle an FT_DIR with location.ItemType=%v: %q", + entry.Location.ItemType, name)) + } + case btrfsitem.FT_SYMLINK: + if entry.Location.ItemType != btrfsitem.INODE_ITEM_KEY { + panic(fmt.Errorf("TODO: I don't know how to handle an FT_SYMLINK with location.ItemType=%v: %q", + entry.Location.ItemType, name)) + } + file, err := subvol.LoadFile(entry.Location.ObjectID) + if err != nil { + printText(out, prefix, isLast, name, textui.Sprintf("%v err=%v", entry.Type, fmtErr(err))) + return + } + printSymlink(out, prefix, isLast, name, file) + case btrfsitem.FT_REG_FILE: + if entry.Location.ItemType != btrfsitem.INODE_ITEM_KEY { + panic(fmt.Errorf("TODO: I don't know how to handle an FT_REG_FILE with location.ItemType=%v: %q", + entry.Location.ItemType, name)) + } + file, err := subvol.LoadFile(entry.Location.ObjectID) + if err != nil { + printText(out, prefix, isLast, name, textui.Sprintf("%v err=%v", entry.Type, fmtErr(err))) + return + } + printFile(out, prefix, isLast, name, file) + case btrfsitem.FT_SOCK: + if entry.Location.ItemType != btrfsitem.INODE_ITEM_KEY { + panic(fmt.Errorf("TODO: I don't know how to handle an FT_SOCK with location.ItemType=%v: %q", + entry.Location.ItemType, name)) + } + file, err := subvol.LoadFile(entry.Location.ObjectID) + if err != nil { + printText(out, prefix, isLast, name, textui.Sprintf("%v err=%v", entry.Type, fmtErr(err))) + return + } + printSocket(out, prefix, isLast, name, file) + case btrfsitem.FT_FIFO: + if entry.Location.ItemType != btrfsitem.INODE_ITEM_KEY { + panic(fmt.Errorf("TODO: I don't know how to handle an FT_FIFO with location.ItemType=%v: %q", + entry.Location.ItemType, name)) + } + file, err := subvol.LoadFile(entry.Location.ObjectID) + if err != nil { + printText(out, prefix, isLast, name, textui.Sprintf("%v err=%v", entry.Type, fmtErr(err))) + return + } + printPipe(out, prefix, isLast, name, file) + default: + panic(fmt.Errorf("TODO: I don't know how to handle a fileType=%v: %q", + entry.Type, name)) + } +} + +func printSymlink(out io.Writer, prefix string, isLast bool, name string, file *btrfs.File) { + var tgt []byte + if file.InodeItem != nil { + var err error + tgt, err = io.ReadAll(io.NewSectionReader(file, 0, file.InodeItem.Size)) + if err != nil { + file.Errs = append(file.Errs, err) + } + } + printText(out, prefix, isLast, name, textui.Sprintf( + "-> %q : %s", + tgt, + fmtInode(file.BareInode))) +} + +func printFile(out io.Writer, prefix string, isLast bool, name string, file *btrfs.File) { + if file.InodeItem != nil { + if _, err := io.Copy(io.Discard, io.NewSectionReader(file, 0, file.InodeItem.Size)); err != nil { + file.Errs = append(file.Errs, err) + } + } + printText(out, prefix, isLast, name, fmtInode(file.BareInode)) +} + +func printSocket(out io.Writer, prefix string, isLast bool, name string, file *btrfs.File) { + if file.InodeItem != nil && file.InodeItem.Size > 0 { + panic(fmt.Errorf("TODO: I don't know how to handle a socket with size>0: %q", name)) + } + printText(out, prefix, isLast, name, fmtInode(file.BareInode)) +} + +func printPipe(out io.Writer, prefix string, isLast bool, name string, file *btrfs.File) { + if file.InodeItem != nil && file.InodeItem.Size > 0 { + panic(fmt.Errorf("TODO: I don't know how to handle a pipe with size>0: %q", name)) + } + printText(out, prefix, isLast, name, fmtInode(file.BareInode)) +} diff --git a/cmd/btrfs-rec/inspect_lsfiles.go b/cmd/btrfs-rec/inspect_lsfiles.go index e9fd057..04b5ec5 100644 --- a/cmd/btrfs-rec/inspect_lsfiles.go +++ b/cmd/btrfs-rec/inspect_lsfiles.go @@ -6,23 +6,14 @@ package main import ( "bufio" - "errors" - "fmt" - "io" "os" - "path" - "strings" - "github.com/datawire/dlib/derror" "github.com/datawire/ocibuild/pkg/cliutil" "github.com/spf13/cobra" + "git.lukeshu.com/btrfs-progs-ng/cmd/btrfs-rec/inspect/lsfiles" "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/btrfsutil" - "git.lukeshu.com/btrfs-progs-ng/lib/maps" - "git.lukeshu.com/btrfs-progs-ng/lib/textui" ) func init() { @@ -37,219 +28,10 @@ func init() { err = _err } }() - defer func() { - if _err := derror.PanicToError(recover()); _err != nil { - textui.Fprintf(out, "\n\n%+v\n", _err) - err = _err - } - }() - ctx := cmd.Context() - printSubvol(out, "", true, "/", btrfs.NewSubvolume( - btrfsutil.NewOldRebuiltForrest(ctx, fs), - btrfsprim.FS_TREE_OBJECTID, - false, - )) - - return nil + return lsfiles.LsFiles( + out, + btrfsutil.NewOldRebuiltForrest(cmd.Context(), fs)) }), }) } - -const ( - tS = "    " - tl = "│   " - tT = "├── " - tL = "└── " -) - -func printText(out io.Writer, prefix string, isLast bool, name, text string) { - first, rest := tT, tl - if isLast { - first, rest = tL, tS - } - for i, line := range strings.Split(textui.Sprintf("%q %s", name, text), "\n") { - _, _ = io.WriteString(out, prefix) - if i == 0 { - _, _ = io.WriteString(out, first) - } else { - _, _ = io.WriteString(out, rest) - } - _, _ = io.WriteString(out, line) - _, _ = io.WriteString(out, "\n") - } -} - -func printSubvol(out io.Writer, prefix string, isLast bool, name string, subvol *btrfs.Subvolume) { - rootInode, err := subvol.GetRootInode() - if err != nil { - printText(out, prefix, isLast, name+"/", textui.Sprintf("subvol_id=%v err=%v", - subvol.TreeID, fmtErr(err))) - return - } - dir, err := subvol.LoadDir(rootInode) - if err != nil { - printText(out, prefix, isLast, name+"/", textui.Sprintf("subvol_id=%v err=%v", - subvol.TreeID, fmtErr(err))) - return - } - if name == "/" { - printDir(out, prefix, isLast, name, dir) - return - } - printText(out, prefix, isLast, name+"/", textui.Sprintf("subvol_id=%v", subvol.TreeID)) - if isLast { - prefix += tS - } else { - prefix += tl - } - printDir(out, prefix, true, name, dir) -} - -func fmtErr(err error) string { - errStr := err.Error() - if strings.Contains(errStr, "\n") { - errStr = "\\\n" + errStr - } - return errStr -} - -func fmtInode(inode btrfs.BareInode) string { - var mode btrfsitem.StatMode - if inode.InodeItem == nil { - inode.Errs = append(inode.Errs, errors.New("missing INODE_ITEM")) - } else { - mode = inode.InodeItem.Mode - } - ret := textui.Sprintf("ino=%v mode=%v", inode.Inode, mode) - if len(inode.Errs) > 0 { - ret += " err=" + fmtErr(inode.Errs) - } - return ret -} - -func printDir(out io.Writer, prefix string, isLast bool, name string, dir *btrfs.Dir) { - printText(out, prefix, isLast, name+"/", fmtInode(dir.BareInode)) - if isLast { - prefix += tS - } else { - prefix += tl - } - for i, childName := range maps.SortedKeys(dir.ChildrenByName) { - printDirEntry( - out, - prefix, - i == len(dir.ChildrenByName)-1, - dir.SV, - path.Join(name, childName), - dir.ChildrenByName[childName]) - } -} - -func printDirEntry(out io.Writer, prefix string, isLast bool, subvol *btrfs.Subvolume, name string, entry btrfsitem.DirEntry) { - if len(entry.Data) != 0 { - panic(fmt.Errorf("TODO: I don't know how to handle dirent.data: %q", name)) - } - switch entry.Type { - case btrfsitem.FT_DIR: - switch entry.Location.ItemType { - case btrfsitem.INODE_ITEM_KEY: - dir, err := subvol.LoadDir(entry.Location.ObjectID) - if err != nil { - printText(out, prefix, isLast, name, textui.Sprintf("%v err=%v", entry.Type, fmtErr(err))) - return - } - printDir(out, prefix, isLast, name, dir) - case btrfsitem.ROOT_ITEM_KEY: - printSubvol(out, prefix, isLast, name, subvol.NewChildSubvolume(entry.Location.ObjectID)) - default: - panic(fmt.Errorf("TODO: I don't know how to handle an FT_DIR with location.ItemType=%v: %q", - entry.Location.ItemType, name)) - } - case btrfsitem.FT_SYMLINK: - if entry.Location.ItemType != btrfsitem.INODE_ITEM_KEY { - panic(fmt.Errorf("TODO: I don't know how to handle an FT_SYMLINK with location.ItemType=%v: %q", - entry.Location.ItemType, name)) - } - file, err := subvol.LoadFile(entry.Location.ObjectID) - if err != nil { - printText(out, prefix, isLast, name, textui.Sprintf("%v err=%v", entry.Type, fmtErr(err))) - return - } - printSymlink(out, prefix, isLast, name, file) - case btrfsitem.FT_REG_FILE: - if entry.Location.ItemType != btrfsitem.INODE_ITEM_KEY { - panic(fmt.Errorf("TODO: I don't know how to handle an FT_REG_FILE with location.ItemType=%v: %q", - entry.Location.ItemType, name)) - } - file, err := subvol.LoadFile(entry.Location.ObjectID) - if err != nil { - printText(out, prefix, isLast, name, textui.Sprintf("%v err=%v", entry.Type, fmtErr(err))) - return - } - printFile(out, prefix, isLast, name, file) - case btrfsitem.FT_SOCK: - if entry.Location.ItemType != btrfsitem.INODE_ITEM_KEY { - panic(fmt.Errorf("TODO: I don't know how to handle an FT_SOCK with location.ItemType=%v: %q", - entry.Location.ItemType, name)) - } - file, err := subvol.LoadFile(entry.Location.ObjectID) - if err != nil { - printText(out, prefix, isLast, name, textui.Sprintf("%v err=%v", entry.Type, fmtErr(err))) - return - } - printSocket(out, prefix, isLast, name, file) - case btrfsitem.FT_FIFO: - if entry.Location.ItemType != btrfsitem.INODE_ITEM_KEY { - panic(fmt.Errorf("TODO: I don't know how to handle an FT_FIFO with location.ItemType=%v: %q", - entry.Location.ItemType, name)) - } - file, err := subvol.LoadFile(entry.Location.ObjectID) - if err != nil { - printText(out, prefix, isLast, name, textui.Sprintf("%v err=%v", entry.Type, fmtErr(err))) - return - } - printPipe(out, prefix, isLast, name, file) - default: - panic(fmt.Errorf("TODO: I don't know how to handle a fileType=%v: %q", - entry.Type, name)) - } -} - -func printSymlink(out io.Writer, prefix string, isLast bool, name string, file *btrfs.File) { - var tgt []byte - if file.InodeItem != nil { - var err error - tgt, err = io.ReadAll(io.NewSectionReader(file, 0, file.InodeItem.Size)) - if err != nil { - file.Errs = append(file.Errs, err) - } - } - printText(out, prefix, isLast, name, textui.Sprintf( - "-> %q : %s", - tgt, - fmtInode(file.BareInode))) -} - -func printFile(out io.Writer, prefix string, isLast bool, name string, file *btrfs.File) { - if file.InodeItem != nil { - if _, err := io.Copy(io.Discard, io.NewSectionReader(file, 0, file.InodeItem.Size)); err != nil { - file.Errs = append(file.Errs, err) - } - } - printText(out, prefix, isLast, name, fmtInode(file.BareInode)) -} - -func printSocket(out io.Writer, prefix string, isLast bool, name string, file *btrfs.File) { - if file.InodeItem != nil && file.InodeItem.Size > 0 { - panic(fmt.Errorf("TODO: I don't know how to handle a socket with size>0: %q", name)) - } - printText(out, prefix, isLast, name, fmtInode(file.BareInode)) -} - -func printPipe(out io.Writer, prefix string, isLast bool, name string, file *btrfs.File) { - if file.InodeItem != nil && file.InodeItem.Size > 0 { - panic(fmt.Errorf("TODO: I don't know how to handle a pipe with size>0: %q", name)) - } - printText(out, prefix, isLast, name, fmtInode(file.BareInode)) -} -- cgit v1.1-4-g5e80 From 8b17537fc562ef422aee7976cf4a44dd040900aa Mon Sep 17 00:00:00 2001 From: Luke Shumaker Date: Sat, 4 Mar 2023 11:07:37 -0700 Subject: btrfsutil: Merge KeyIO in to RebuiltForrest --- cmd/btrfs-rec/inspect/rebuildtrees/rebuild.go | 10 ++--- lib/btrfsutil/rebuilt_forrest.go | 19 ++++++++-- lib/btrfsutil/rebuilt_readitem.go | 53 +++++++-------------------- lib/btrfsutil/rebuilt_tree.go | 2 +- 4 files changed, 33 insertions(+), 51 deletions(-) diff --git a/cmd/btrfs-rec/inspect/rebuildtrees/rebuild.go b/cmd/btrfs-rec/inspect/rebuildtrees/rebuild.go index 4937ee3..01e4e3c 100644 --- a/cmd/btrfs-rec/inspect/rebuildtrees/rebuild.go +++ b/cmd/btrfs-rec/inspect/rebuildtrees/rebuild.go @@ -47,8 +47,7 @@ func (o keyAndTree) String() string { } type rebuilder struct { - scan ScanDevicesResult - keyIO *btrfsutil.KeyIO + scan ScanDevicesResult rebuilt *btrfsutil.RebuiltForrest @@ -83,13 +82,10 @@ func NewRebuilder(ctx context.Context, fs *btrfs.FS, nodeList []btrfsvol.Logical return nil, err } - keyIO := btrfsutil.NewKeyIO(fs, scanData.Superblock, scanData.Graph) - o := &rebuilder{ - scan: scanData, - keyIO: keyIO, + scan: scanData, } - o.rebuilt = btrfsutil.NewRebuiltForrest(scanData.Superblock, scanData.Graph, keyIO, forrestCallbacks{o}) + o.rebuilt = btrfsutil.NewRebuiltForrest(fs, scanData.Superblock, scanData.Graph, forrestCallbacks{o}) return o, nil } diff --git a/lib/btrfsutil/rebuilt_forrest.go b/lib/btrfsutil/rebuilt_forrest.go index 0e8f5ad..25d953b 100644 --- a/lib/btrfsutil/rebuilt_forrest.go +++ b/lib/btrfsutil/rebuilt_forrest.go @@ -6,6 +6,7 @@ package btrfsutil import ( "context" + "sync" "github.com/datawire/dlib/dlog" @@ -14,6 +15,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" ) @@ -57,26 +59,30 @@ type RebuiltForrestCallbacks interface { // 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 { +func NewRebuiltForrest(file diskio.File[btrfsvol.LogicalAddr], sb btrfstree.Superblock, graph Graph, cb RebuiltForrestCallbacks) *RebuiltForrest { return &RebuiltForrest{ + file: file, sb: sb, graph: graph, - keyIO: keyIO, cb: cb, trees: make(map[btrfsprim.ObjID]*RebuiltTree), @@ -89,6 +95,13 @@ 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() + }, + }, } } diff --git a/lib/btrfsutil/rebuilt_readitem.go b/lib/btrfsutil/rebuilt_readitem.go index 7e9be09..68aabdd 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,43 +26,19 @@ func (ptr ItemPtr) String() string { return fmt.Sprintf("node@%v[%v]", ptr.Node, ptr.Slot) } -type KeyIO struct { - rawFile diskio.File[btrfsvol.LogicalAddr] - sb btrfstree.Superblock - graph Graph - - mu sync.Mutex - cache containers.ARCache[btrfsvol.LogicalAddr, *btrfstree.Node] -} - -func NewKeyIO(file diskio.File[btrfsvol.LogicalAddr], sb btrfstree.Superblock, graph Graph) *KeyIO { - return &KeyIO{ - rawFile: file, - sb: sb, - graph: graph, - - cache: containers.ARCache[btrfsvol.LogicalAddr, *btrfstree.Node]{ - MaxLen: textui.Tunable(8), - OnRemove: func(_ btrfsvol.LogicalAddr, node *btrfstree.Node) { - node.Free() - }, - }, - } -} - -func (o *KeyIO) readNode(ctx context.Context, laddr 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) - node, err := btrfstree.ReadNode[btrfsvol.LogicalAddr](o.rawFile, o.sb, laddr, btrfstree.NodeExpectations{ + node, err := btrfstree.ReadNode[btrfsvol.LogicalAddr](ts.file, ts.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}, @@ -83,23 +56,23 @@ func (o *KeyIO) readNode(ctx context.Context, laddr btrfsvol.LogicalAddr) *btrfs panic(fmt.Errorf("should not happen: i/o error: %w", err)) } - o.cache.Store(laddr, node) + ts.nodes.Store(laddr, node) 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).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..820913e 100644 --- a/lib/btrfsutil/rebuilt_tree.go +++ b/lib/btrfsutil/rebuilt_tree.go @@ -329,7 +329,7 @@ func (tree *RebuiltTree) ReadItem(ctx context.Context, key btrfsprim.Key) btrfsi 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 -- cgit v1.1-4-g5e80 From 33de7f09d31063ef2a4380bb2f2692653a6de06c Mon Sep 17 00:00:00 2001 From: Luke Shumaker Date: Thu, 9 Mar 2023 16:43:39 -0700 Subject: containers: Add OptionalValue and OptionalNil --- cmd/btrfs-rec/inspect/rebuildmappings/process.go | 5 +---- .../inspect/rebuildmappings/process_matchsums_exact.go | 5 +---- .../inspect/rebuildmappings/process_matchsums_fuzzy.go | 5 +---- cmd/btrfs-rec/inspect/rebuildtrees/scan.go | 2 +- cmd/btrfs-rec/inspect_lstrees.go | 2 +- lib/btrfs/btrfsitem/item_chunk.go | 5 +---- lib/btrfs/btrfstree/readnode.go | 10 +++++----- lib/btrfsutil/graph.go | 2 +- lib/btrfsutil/old_rebuilt_forrest.go | 10 +++++----- lib/btrfsutil/rebuilt_readitem.go | 10 +++++----- lib/containers/optional.go | 13 +++++++++++++ 11 files changed, 35 insertions(+), 34 deletions(-) diff --git a/cmd/btrfs-rec/inspect/rebuildmappings/process.go b/cmd/btrfs-rec/inspect/rebuildmappings/process.go index e42acf9..7a49cc6 100644 --- a/cmd/btrfs-rec/inspect/rebuildmappings/process.go +++ b/cmd/btrfs-rec/inspect/rebuildmappings/process.go @@ -137,10 +137,7 @@ func RebuildMappings(ctx context.Context, fs *btrfs.FS, scanResults ScanDevicesR PAddr: otherPAddr.Add(-offsetWithinChunk), Size: bg.Size, SizeLocked: true, - Flags: containers.Optional[btrfsvol.BlockGroupFlags]{ - OK: true, - Val: bg.Flags, - }, + Flags: containers.OptionalValue(bg.Flags), } if err := fs.LV.AddMapping(mapping); err != nil { dlog.Errorf(ctx, "error: adding flags from blockgroup: %v", err) diff --git a/cmd/btrfs-rec/inspect/rebuildmappings/process_matchsums_exact.go b/cmd/btrfs-rec/inspect/rebuildmappings/process_matchsums_exact.go index ef9d9aa..5148e5c 100644 --- a/cmd/btrfs-rec/inspect/rebuildmappings/process_matchsums_exact.go +++ b/cmd/btrfs-rec/inspect/rebuildmappings/process_matchsums_exact.go @@ -63,10 +63,7 @@ func matchBlockGroupSumsExact(ctx context.Context, PAddr: matches[0], Size: blockgroup.Size, SizeLocked: true, - Flags: containers.Optional[btrfsvol.BlockGroupFlags]{ - OK: true, - Val: blockgroup.Flags, - }, + Flags: containers.OptionalValue(blockgroup.Flags), } if err := fs.LV.AddMapping(mapping); err != nil { dlog.Errorf(ctx, "error: %v", err) diff --git a/cmd/btrfs-rec/inspect/rebuildmappings/process_matchsums_fuzzy.go b/cmd/btrfs-rec/inspect/rebuildmappings/process_matchsums_fuzzy.go index 905211c..f3557cd 100644 --- a/cmd/btrfs-rec/inspect/rebuildmappings/process_matchsums_fuzzy.go +++ b/cmd/btrfs-rec/inspect/rebuildmappings/process_matchsums_fuzzy.go @@ -123,10 +123,7 @@ func matchBlockGroupSumsFuzzy(ctx context.Context, PAddr: best.Dat[0].PAddr, Size: blockgroup.Size, SizeLocked: true, - Flags: containers.Optional[btrfsvol.BlockGroupFlags]{ - OK: true, - Val: blockgroup.Flags, - }, + Flags: containers.OptionalValue(blockgroup.Flags), } if err := fs.LV.AddMapping(mapping); err != nil { dlog.Errorf(ctx, "error: %v", err) diff --git a/cmd/btrfs-rec/inspect/rebuildtrees/scan.go b/cmd/btrfs-rec/inspect/rebuildtrees/scan.go index 961ff8d..ada9f6f 100644 --- a/cmd/btrfs-rec/inspect/rebuildtrees/scan.go +++ b/cmd/btrfs-rec/inspect/rebuildtrees/scan.go @@ -72,7 +72,7 @@ func ScanDevices(ctx context.Context, fs *btrfs.FS, nodeList []btrfsvol.LogicalA return ScanDevicesResult{}, err } node, 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 { node.Free() diff --git a/cmd/btrfs-rec/inspect_lstrees.go b/cmd/btrfs-rec/inspect_lstrees.go index 1541012..cad1a37 100644 --- a/cmd/btrfs-rec/inspect_lstrees.go +++ b/cmd/btrfs-rec/inspect_lstrees.go @@ -106,7 +106,7 @@ func init() { } visitedNodes.Insert(laddr) node, 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 { treeErrCnt++ 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/readnode.go b/lib/btrfs/btrfstree/readnode.go index c5d9145..c2e3b0f 100644 --- a/lib/btrfs/btrfstree/readnode.go +++ b/lib/btrfs/btrfstree/readnode.go @@ -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/btrfsutil/graph.go b/lib/btrfsutil/graph.go index 45e9878..35848de 100644 --- a/lib/btrfsutil/graph.go +++ b/lib/btrfsutil/graph.go @@ -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/old_rebuilt_forrest.go b/lib/btrfsutil/old_rebuilt_forrest.go index c146935..abe3329 100644 --- a/lib/btrfsutil/old_rebuilt_forrest.go +++ b/lib/btrfsutil/old_rebuilt_forrest.go @@ -247,9 +247,9 @@ func (bt *OldRebuiltForrest) readNode(nodeInfo nodeInfo) *btrfstree.Node { } node, err := btrfstree.ReadNode[btrfsvol.LogicalAddr](bt.inner, *sb, nodeInfo.LAddr, btrfstree.NodeExpectations{ - LAddr: containers.Optional[btrfsvol.LogicalAddr]{OK: true, Val: nodeInfo.LAddr}, - Level: containers.Optional[uint8]{OK: true, Val: nodeInfo.Level}, - Generation: containers.Optional[btrfsprim.Generation]{OK: true, Val: nodeInfo.Generation}, + 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", @@ -257,8 +257,8 @@ func (bt *OldRebuiltForrest) readNode(nodeInfo nodeInfo) *btrfstree.Node { } return nil }, - MinItem: containers.Optional[btrfsprim.Key]{OK: true, Val: nodeInfo.MinItem}, - MaxItem: containers.Optional[btrfsprim.Key]{OK: true, Val: nodeInfo.MaxItem}, + MinItem: containers.OptionalValue(nodeInfo.MinItem), + MaxItem: containers.OptionalValue(nodeInfo.MaxItem), }) if err != nil { panic(fmt.Errorf("should not happen: i/o error: %w", err)) diff --git a/lib/btrfsutil/rebuilt_readitem.go b/lib/btrfsutil/rebuilt_readitem.go index 68aabdd..ff919f0 100644 --- a/lib/btrfsutil/rebuilt_readitem.go +++ b/lib/btrfsutil/rebuilt_readitem.go @@ -39,9 +39,9 @@ func (ts *RebuiltForrest) readNode(ctx context.Context, laddr btrfsvol.LogicalAd dlog.Debugf(ctx, "cache-miss node@%v, reading...", laddr) node, err := btrfstree.ReadNode[btrfsvol.LogicalAddr](ts.file, ts.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}, + 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", @@ -49,8 +49,8 @@ func (ts *RebuiltForrest) readNode(ctx context.Context, laddr btrfsvol.LogicalAd } 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)) 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) -- cgit v1.1-4-g5e80 From 5d25e2449110ca37eb1f0f5b0290f2868c21ac2a Mon Sep 17 00:00:00 2001 From: Luke Shumaker Date: Sat, 4 Mar 2023 14:02:16 -0700 Subject: rebuildnodes/btrees: Rename methods to make API structure clearer --- cmd/btrfs-rec/inspect/rebuildtrees/rebuild.go | 22 ++++---- .../inspect/rebuildtrees/rebuild_treecb.go | 4 +- .../inspect/rebuildtrees/rebuild_wantcb.go | 34 ++++++------- lib/btrfsutil/rebuilt_forrest.go | 51 ++++++++++++------- lib/btrfsutil/rebuilt_tree.go | 58 +++++++++++----------- 5 files changed, 91 insertions(+), 78 deletions(-) diff --git a/cmd/btrfs-rec/inspect/rebuildtrees/rebuild.go b/cmd/btrfs-rec/inspect/rebuildtrees/rebuild.go index 01e4e3c..0d25ac3 100644 --- a/cmd/btrfs-rec/inspect/rebuildtrees/rebuild.go +++ b/cmd/btrfs-rec/inspect/rebuildtrees/rebuild.go @@ -90,7 +90,7 @@ func NewRebuilder(ctx context.Context, fs *btrfs.FS, nodeList []btrfsvol.Logical } func (o *rebuilder) ListRoots(ctx context.Context) map[btrfsprim.ObjID]containers.Set[btrfsvol.LogicalAddr] { - return o.rebuilt.ListRoots(ctx) + return o.rebuilt.RebuiltListRoots(ctx) } func (o *rebuilder) Rebuild(ctx context.Context) error { @@ -159,7 +159,7 @@ func (o *rebuilder) processTreeQueue(ctx context.Context) error { } // This will call o.AddedItem as nescessary, which // inserts to o.addedItemQueue. - _ = o.rebuilt.Tree(ctx, o.curKey.TreeID) + _ = o.rebuilt.RebuiltTree(ctx, o.curKey.TreeID) } return nil @@ -197,18 +197,18 @@ func (o *rebuilder) processAddedItemQueue(ctx context.Context) error { progressWriter.Set(progress) ctx := dlog.WithField(ctx, "btrfs.inspect.rebuild-trees.rebuild.settle.item", key) - tree := o.rebuilt.Tree(ctx, key.TreeID) - incPtr, ok := tree.Items(ctx).Load(key.Key) + tree := o.rebuilt.RebuiltTree(ctx, key.TreeID) + incPtr, ok := tree.RebuiltItems(ctx).Load(key.Key) if !ok { panic(fmt.Errorf("should not happen: failed to load already-added item: %v", key)) } - excPtr, ok := tree.PotentialItems(ctx).Load(key.Key) - if ok && tree.ShouldReplace(incPtr.Node, excPtr.Node) { + excPtr, ok := tree.RebuiltPotentialItems(ctx).Load(key.Key) + if ok && tree.RebuiltShouldReplace(incPtr.Node, excPtr.Node) { wantKey := wantWithTree{ TreeID: key.TreeID, Key: wantFromKey(key.Key), } - o.wantAugment(ctx, wantKey, tree.LeafToRoots(ctx, excPtr.Node)) + o.wantAugment(ctx, wantKey, tree.RebuiltLeafToRoots(ctx, excPtr.Node)) progress.NumAugments = o.numAugments progress.NumAugmentTrees = len(o.augmentQueue) progressWriter.Set(progress) @@ -266,7 +266,7 @@ func (o *rebuilder) processSettledItemQueue(ctx context.Context) error { ctx := dlog.WithField(ctx, "btrfs.inspect.rebuild-trees.rebuild.process.item", key) item := keyAndBody{ keyAndTree: key, - Body: o.rebuilt.Tree(ctx, key.TreeID).ReadItem(ctx, key.Key), + Body: o.rebuilt.RebuiltTree(ctx, key.TreeID).ReadItem(ctx, key.Key), } select { case itemChan <- item: @@ -333,7 +333,7 @@ func (o *rebuilder) processAugmentQueue(ctx context.Context) error { progressWriter.Set(progress) // This will call o.AddedItem as nescessary, which // inserts to o.addedItemQueue. - o.rebuilt.Tree(ctx, treeID).AddRoot(ctx, nodeAddr) + o.rebuilt.RebuiltTree(ctx, treeID).RebuiltAddRoot(ctx, nodeAddr) progress.N++ } } @@ -381,7 +381,7 @@ func (o *rebuilder) resolveTreeAugments(ctx context.Context, treeID btrfsprim.Ob } else { choices[choice] = ChoiceInfo{ Count: 1, - Distance: discardOK(o.rebuilt.Tree(ctx, treeID).COWDistance(o.scan.Graph.Nodes[choice].Owner)), + Distance: discardOK(o.rebuilt.RebuiltTree(ctx, treeID).RebuiltCOWDistance(o.scan.Graph.Nodes[choice].Owner)), Generation: o.scan.Graph.Nodes[choice].Generation, } } @@ -395,7 +395,7 @@ func (o *rebuilder) resolveTreeAugments(ctx context.Context, treeID btrfsprim.Ob } else { choices[choice] = ChoiceInfo{ Count: 1, - Distance: discardOK(o.rebuilt.Tree(ctx, treeID).COWDistance(o.scan.Graph.Nodes[choice].Owner)), + Distance: discardOK(o.rebuilt.RebuiltTree(ctx, treeID).RebuiltCOWDistance(o.scan.Graph.Nodes[choice].Owner)), Generation: o.scan.Graph.Nodes[choice].Generation, } } diff --git a/cmd/btrfs-rec/inspect/rebuildtrees/rebuild_treecb.go b/cmd/btrfs-rec/inspect/rebuildtrees/rebuild_treecb.go index 765ee76..92b5ee5 100644 --- a/cmd/btrfs-rec/inspect/rebuildtrees/rebuild_treecb.go +++ b/cmd/btrfs-rec/inspect/rebuildtrees/rebuild_treecb.go @@ -48,7 +48,7 @@ func (o forrestCallbacks) LookupRoot(ctx context.Context, tree btrfsprim.ObjID) o.enqueueRetry(btrfsprim.ROOT_TREE_OBJECTID) return 0, btrfsitem.Root{}, false } - itemBody := o.rebuilt.Tree(ctx, wantKey.TreeID).ReadItem(ctx, foundKey) + itemBody := o.rebuilt.RebuiltTree(ctx, wantKey.TreeID).ReadItem(ctx, foundKey) defer itemBody.Free() switch itemBody := itemBody.(type) { case *btrfsitem.Root: @@ -74,7 +74,7 @@ func (o forrestCallbacks) LookupUUID(ctx context.Context, uuid btrfsprim.UUID) ( o.enqueueRetry(btrfsprim.UUID_TREE_OBJECTID) return 0, false } - itemBody := o.rebuilt.Tree(ctx, wantKey.TreeID).ReadItem(ctx, wantKey.Key.Key()) + itemBody := o.rebuilt.RebuiltTree(ctx, wantKey.TreeID).ReadItem(ctx, wantKey.Key.Key()) defer itemBody.Free() switch itemBody := itemBody.(type) { case *btrfsitem.UUIDMap: diff --git a/cmd/btrfs-rec/inspect/rebuildtrees/rebuild_wantcb.go b/cmd/btrfs-rec/inspect/rebuildtrees/rebuild_wantcb.go index 8bfdd06..eff2a83 100644 --- a/cmd/btrfs-rec/inspect/rebuildtrees/rebuild_wantcb.go +++ b/cmd/btrfs-rec/inspect/rebuildtrees/rebuild_wantcb.go @@ -43,7 +43,7 @@ func (o graphCallbacks) Want(ctx context.Context, reason string, treeID btrfspri } func (o *rebuilder) _want(ctx context.Context, wantKey wantWithTree) (key btrfsprim.Key, ok bool) { - if o.rebuilt.Tree(ctx, wantKey.TreeID) == nil { + if o.rebuilt.RebuiltTree(ctx, wantKey.TreeID) == nil { o.enqueueRetry(wantKey.TreeID) return btrfsprim.Key{}, false } @@ -51,7 +51,7 @@ func (o *rebuilder) _want(ctx context.Context, wantKey wantWithTree) (key btrfsp // check if we already have it tgt := wantKey.Key.Key() - if key, _, ok := o.rebuilt.Tree(ctx, wantKey.TreeID).Items(ctx).Search(func(key btrfsprim.Key, _ btrfsutil.ItemPtr) int { + if key, _, ok := o.rebuilt.RebuiltTree(ctx, wantKey.TreeID).RebuiltItems(ctx).Search(func(key btrfsprim.Key, _ btrfsutil.ItemPtr) int { key.Offset = 0 return tgt.Compare(key) }); ok { @@ -64,13 +64,13 @@ func (o *rebuilder) _want(ctx context.Context, wantKey wantWithTree) (key btrfsp return btrfsprim.Key{}, false } wants := make(containers.Set[btrfsvol.LogicalAddr]) - o.rebuilt.Tree(ctx, wantKey.TreeID).PotentialItems(ctx).Subrange( + o.rebuilt.RebuiltTree(ctx, wantKey.TreeID).RebuiltPotentialItems(ctx).Subrange( func(k btrfsprim.Key, _ btrfsutil.ItemPtr) int { k.Offset = 0 return tgt.Compare(k) }, func(_ btrfsprim.Key, v btrfsutil.ItemPtr) bool { - wants.InsertFrom(o.rebuilt.Tree(ctx, wantKey.TreeID).LeafToRoots(ctx, v.Node)) + wants.InsertFrom(o.rebuilt.RebuiltTree(ctx, wantKey.TreeID).RebuiltLeafToRoots(ctx, v.Node)) return true }) o.wantAugment(ctx, wantKey, wants) @@ -93,7 +93,7 @@ func (o graphCallbacks) WantOff(ctx context.Context, reason string, treeID btrfs } func (o *rebuilder) _wantOff(ctx context.Context, wantKey wantWithTree) (ok bool) { - if o.rebuilt.Tree(ctx, wantKey.TreeID) == nil { + if o.rebuilt.RebuiltTree(ctx, wantKey.TreeID) == nil { o.enqueueRetry(wantKey.TreeID) return false } @@ -101,7 +101,7 @@ func (o *rebuilder) _wantOff(ctx context.Context, wantKey wantWithTree) (ok bool // check if we already have it tgt := wantKey.Key.Key() - if _, ok := o.rebuilt.Tree(ctx, wantKey.TreeID).Items(ctx).Load(tgt); ok { + if _, ok := o.rebuilt.RebuiltTree(ctx, wantKey.TreeID).RebuiltItems(ctx).Load(tgt); ok { return true } @@ -111,10 +111,10 @@ func (o *rebuilder) _wantOff(ctx context.Context, wantKey wantWithTree) (ok bool return false } wants := make(containers.Set[btrfsvol.LogicalAddr]) - o.rebuilt.Tree(ctx, wantKey.TreeID).PotentialItems(ctx).Subrange( + o.rebuilt.RebuiltTree(ctx, wantKey.TreeID).RebuiltPotentialItems(ctx).Subrange( func(k btrfsprim.Key, _ btrfsutil.ItemPtr) int { return tgt.Compare(k) }, func(_ btrfsprim.Key, v btrfsutil.ItemPtr) bool { - wants.InsertFrom(o.rebuilt.Tree(ctx, wantKey.TreeID).LeafToRoots(ctx, v.Node)) + wants.InsertFrom(o.rebuilt.RebuiltTree(ctx, wantKey.TreeID).RebuiltLeafToRoots(ctx, v.Node)) return true }) o.wantAugment(ctx, wantKey, wants) @@ -134,7 +134,7 @@ func (o graphCallbacks) WantDirIndex(ctx context.Context, reason string, treeID } ctx = withWant(ctx, logFieldItemWant, reason, wantKey) - if o.rebuilt.Tree(ctx, treeID) == nil { + if o.rebuilt.RebuiltTree(ctx, treeID) == nil { o.enqueueRetry(treeID) return } @@ -143,7 +143,7 @@ func (o graphCallbacks) WantDirIndex(ctx context.Context, reason string, treeID tgt := wantKey.Key.Key() found := false - o.rebuilt.Tree(ctx, treeID).Items(ctx).Subrange( + o.rebuilt.RebuiltTree(ctx, treeID).RebuiltItems(ctx).Subrange( func(key btrfsprim.Key, _ btrfsutil.ItemPtr) int { key.Offset = 0 return tgt.Compare(key) @@ -164,14 +164,14 @@ func (o graphCallbacks) WantDirIndex(ctx context.Context, reason string, treeID return } wants := make(containers.Set[btrfsvol.LogicalAddr]) - o.rebuilt.Tree(ctx, treeID).PotentialItems(ctx).Subrange( + o.rebuilt.RebuiltTree(ctx, treeID).RebuiltPotentialItems(ctx).Subrange( func(key btrfsprim.Key, _ btrfsutil.ItemPtr) int { key.Offset = 0 return tgt.Compare(key) }, func(_ btrfsprim.Key, ptr btrfsutil.ItemPtr) bool { if itemName, ok := o.scan.Names[ptr]; ok && bytes.Equal(itemName, name) { - wants.InsertFrom(o.rebuilt.Tree(ctx, treeID).LeafToRoots(ctx, ptr.Node)) + wants.InsertFrom(o.rebuilt.RebuiltTree(ctx, treeID).RebuiltLeafToRoots(ctx, ptr.Node)) } return true }) @@ -259,7 +259,7 @@ func (o graphCallbacks) _wantRange( ctx = withWant(ctx, logFieldItemWant, reason, wantKey) wantKey.Key.OffsetType = offsetRange - if o.rebuilt.Tree(ctx, treeID) == nil { + if o.rebuilt.RebuiltTree(ctx, treeID) == nil { o.enqueueRetry(treeID) return } @@ -275,7 +275,7 @@ func (o graphCallbacks) _wantRange( }) o._walkRange( ctx, - o.rebuilt.Tree(ctx, treeID).Items(ctx), + o.rebuilt.RebuiltTree(ctx, treeID).RebuiltItems(ctx), treeID, objID, typ, beg, end, func(runKey btrfsprim.Key, _ btrfsutil.ItemPtr, runBeg, runEnd uint64) { var overlappingGaps []*containers.RBNode[gap] @@ -320,7 +320,7 @@ func (o graphCallbacks) _wantRange( if gaps.Len() == 0 { return } - potentialItems := o.rebuilt.Tree(ctx, treeID).PotentialItems(ctx) + potentialItems := o.rebuilt.RebuiltTree(ctx, treeID).RebuiltPotentialItems(ctx) gaps.Range(func(rbNode *containers.RBNode[gap]) bool { gap := rbNode.Value last := gap.Beg @@ -340,7 +340,7 @@ func (o graphCallbacks) _wantRange( wantKey.Key.OffsetLow = gap.Beg wantKey.Key.OffsetHigh = gap.End wantCtx := withWant(ctx, logFieldItemWant, reason, wantKey) - o.wantAugment(wantCtx, wantKey, o.rebuilt.Tree(wantCtx, treeID).LeafToRoots(wantCtx, v.Node)) + o.wantAugment(wantCtx, wantKey, o.rebuilt.RebuiltTree(wantCtx, treeID).RebuiltLeafToRoots(wantCtx, v.Node)) last = runEnd }) if last < gap.End { @@ -372,7 +372,7 @@ func (o graphCallbacks) WantCSum(ctx context.Context, reason string, inodeTree, o.enqueueRetry(inodeTree) return } - inodePtr, ok := o.rebuilt.Tree(inodeCtx, inodeTree).Items(inodeCtx).Load(inodeWant.Key.Key()) + inodePtr, ok := o.rebuilt.RebuiltTree(inodeCtx, inodeTree).RebuiltItems(inodeCtx).Load(inodeWant.Key.Key()) if !ok { panic(fmt.Errorf("should not happen: could not load key: %v", inodeWant)) } diff --git a/lib/btrfsutil/rebuilt_forrest.go b/lib/btrfsutil/rebuilt_forrest.go index 25d953b..de18080 100644 --- a/lib/btrfsutil/rebuilt_forrest.go +++ b/lib/btrfsutil/rebuilt_forrest.go @@ -30,10 +30,9 @@ type RebuiltForrestCallbacks interface { // 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 @@ -49,11 +48,24 @@ type RebuiltForrestCallbacks interface { // 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 .COWDistance() method to compare how related two -// trees are +// - 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. +// +// .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(). @@ -105,12 +117,15 @@ func NewRebuiltForrest(file diskio.File[btrfsvol.LogicalAddr], sb btrfstree.Supe } } -// 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) { @@ -125,8 +140,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 } }() @@ -185,7 +200,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 @@ -201,12 +216,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_tree.go b/lib/btrfsutil/rebuilt_tree.go index 820913e..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.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) -- cgit v1.1-4-g5e80 From 3fea600da8e033abb7e415694e53aaf0787ed95c Mon Sep 17 00:00:00 2001 From: Luke Shumaker Date: Sat, 4 Mar 2023 13:14:18 -0700 Subject: btrfsutil: RebuiltForrest: Accept nil callbacks --- lib/btrfsutil/rebuilt_forrest.go | 72 ++++++++++++++++++++++++++++++++++++++-- 1 file changed, 69 insertions(+), 3 deletions(-) diff --git a/lib/btrfsutil/rebuilt_forrest.go b/lib/btrfsutil/rebuilt_forrest.go index de18080..b5c646d 100644 --- a/lib/btrfsutil/rebuilt_forrest.go +++ b/lib/btrfsutil/rebuilt_forrest.go @@ -6,6 +6,7 @@ package btrfsutil import ( "context" + "fmt" "sync" "github.com/datawire/dlib/dlog" @@ -27,6 +28,65 @@ 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. // @@ -88,10 +148,10 @@ type RebuiltForrest struct { nodes containers.ARCache[btrfsvol.LogicalAddr, *btrfstree.Node] } -// NewRebuiltForrest returns a new RebuiltForrest instance. All of -// the callbacks must be non-nil. +// 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 { - return &RebuiltForrest{ + ret := &RebuiltForrest{ file: file, sb: sb, graph: graph, @@ -115,6 +175,12 @@ func NewRebuiltForrest(file diskio.File[btrfsvol.LogicalAddr], sb btrfstree.Supe }, }, } + if ret.cb == nil { + ret.cb = noopRebuiltForrestCallbacks{ + forrest: ret, + } + } + return ret } // RebuiltTree returns a given tree, initializing it if nescessary. -- cgit v1.1-4-g5e80