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. --- 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 +++++++++++------------ 6 files changed, 66 insertions(+), 69 deletions(-) (limited to 'lib/btrfsutil') 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, -- cgit v1.2.3-2-g168b 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(-) (limited to 'lib/btrfsutil') 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.2.3-2-g168b 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(-) (limited to 'lib/btrfsutil') 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.2.3-2-g168b 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 (limited to 'lib/btrfsutil') 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.2.3-2-g168b 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 --- lib/btrfsutil/graph.go | 4 +-- lib/btrfsutil/rebuilt_readitem.go | 69 ++------------------------------------- 2 files changed, 4 insertions(+), 69 deletions(-) (limited to 'lib/btrfsutil') 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.2.3-2-g168b 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 (limited to 'lib/btrfsutil') 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.2.3-2-g168b 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. --- lib/btrfsutil/old_rebuilt_forrest.go | 10 +++++----- lib/btrfsutil/rebuilt_forrest.go | 2 +- lib/btrfsutil/walk.go | 4 ++-- 3 files changed, 8 insertions(+), 8 deletions(-) (limited to 'lib/btrfsutil') 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.2.3-2-g168b 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(-) (limited to 'lib/btrfsutil') 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.2.3-2-g168b 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(-) (limited to 'lib/btrfsutil') 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.2.3-2-g168b 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 --- lib/btrfsutil/rebuilt_forrest.go | 19 +++++++++++--- lib/btrfsutil/rebuilt_readitem.go | 53 ++++++++++----------------------------- lib/btrfsutil/rebuilt_tree.go | 2 +- 3 files changed, 30 insertions(+), 44 deletions(-) (limited to 'lib/btrfsutil') 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.2.3-2-g168b 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 --- lib/btrfsutil/graph.go | 2 +- lib/btrfsutil/old_rebuilt_forrest.go | 10 +++++----- lib/btrfsutil/rebuilt_readitem.go | 10 +++++----- 3 files changed, 11 insertions(+), 11 deletions(-) (limited to 'lib/btrfsutil') 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)) -- cgit v1.2.3-2-g168b 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 --- lib/btrfsutil/rebuilt_forrest.go | 51 ++++++++++++++++++++++------------- lib/btrfsutil/rebuilt_tree.go | 58 +++++++++++++++++++--------------------- 2 files changed, 61 insertions(+), 48 deletions(-) (limited to 'lib/btrfsutil') 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.2.3-2-g168b 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(-) (limited to 'lib/btrfsutil') 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.2.3-2-g168b