diff options
5 files changed, 191 insertions, 178 deletions
diff --git a/lib/btrfsprogs/btrfsinspect/rebuildnodes/btrees/rebuilt_btrees.go b/lib/btrfsprogs/btrfsinspect/rebuildnodes/btrees/rebuilt_btrees.go index 6e68a84..613f3ca 100644 --- a/lib/btrfsprogs/btrfsinspect/rebuildnodes/btrees/rebuilt_btrees.go +++ b/lib/btrfsprogs/btrfsinspect/rebuildnodes/btrees/rebuilt_btrees.go @@ -16,18 +16,13 @@ import ( "git.lukeshu.com/btrfs-progs-ng/lib/btrfs/btrfstree" "git.lukeshu.com/btrfs-progs-ng/lib/btrfs/btrfsvol" pkggraph "git.lukeshu.com/btrfs-progs-ng/lib/btrfsprogs/btrfsinspect/rebuildnodes/graph" + "git.lukeshu.com/btrfs-progs-ng/lib/btrfsprogs/btrfsinspect/rebuildnodes/keyio" "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" ) -type itemPtr struct { - Node btrfsvol.LogicalAddr - Idx int -} - type rebuiltTree struct { // static ID btrfsprim.ObjID @@ -39,7 +34,7 @@ type rebuiltTree struct { // mutable Roots containers.Set[btrfsvol.LogicalAddr] - Items containers.SortedMap[btrfsprim.Key, itemPtr] + Items containers.SortedMap[btrfsprim.Key, keyio.ItemPtr] } // isOwnerOK returns whether it is permissible for a node with @@ -85,9 +80,9 @@ func (tree *rebuiltTree) isOwnerOK(owner btrfsprim.ObjID) bool { // NewRebuiltTrees(). type RebuiltTrees struct { // static - rawFile diskio.File[btrfsvol.LogicalAddr] - sb btrfstree.Superblock - graph pkggraph.Graph + sb btrfstree.Superblock + graph pkggraph.Graph + keyIO keyio.Handle // static callbacks cbAddedItem func(ctx context.Context, tree btrfsprim.ObjID, key btrfsprim.Key) @@ -95,63 +90,28 @@ type RebuiltTrees struct { cbLookupUUID func(ctx context.Context, uuid btrfsprim.UUID) (id btrfsprim.ObjID, ok bool) // mutable - trees map[btrfsprim.ObjID]*rebuiltTree - nodeCache *containers.LRUCache[btrfsvol.LogicalAddr, *diskio.Ref[btrfsvol.LogicalAddr, btrfstree.Node]] + trees map[btrfsprim.ObjID]*rebuiltTree } // NewRebuiltTrees returns a new RebuiltTrees instance. All of the // callbacks must be non-nil. func NewRebuiltTrees( - file diskio.File[btrfsvol.LogicalAddr], sb btrfstree.Superblock, graph pkggraph.Graph, + sb btrfstree.Superblock, graph pkggraph.Graph, keyIO keyio.Handle, cbAddedItem func(ctx context.Context, tree btrfsprim.ObjID, key btrfsprim.Key), cbLookupRoot func(ctx context.Context, tree btrfsprim.ObjID) (item btrfsitem.Root, ok bool), cbLookupUUID func(ctx context.Context, uuid btrfsprim.UUID) (id btrfsprim.ObjID, ok bool), ) *RebuiltTrees { return &RebuiltTrees{ - rawFile: file, - sb: sb, - graph: graph, + sb: sb, + graph: graph, + keyIO: keyIO, cbAddedItem: cbAddedItem, cbLookupRoot: cbLookupRoot, cbLookupUUID: cbLookupUUID, - trees: make(map[btrfsprim.ObjID]*rebuiltTree), - nodeCache: containers.NewLRUCache[btrfsvol.LogicalAddr, *diskio.Ref[btrfsvol.LogicalAddr, btrfstree.Node]](8), - } -} - -func (ts *RebuiltTrees) readNode(laddr btrfsvol.LogicalAddr) *diskio.Ref[btrfsvol.LogicalAddr, btrfstree.Node] { - if cached, ok := ts.nodeCache.Get(laddr); ok { - return cached - } - - 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)) + trees: make(map[btrfsprim.ObjID]*rebuiltTree), } - - ref, err := btrfstree.ReadNode(ts.rawFile, 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}, - Owner: func(treeID btrfsprim.ObjID) error { - if treeID != graphInfo.Owner { - return fmt.Errorf("expected owner=%v but claims to have owner=%v", - graphInfo.Owner, treeID) - } - return nil - }, - MinItem: containers.Optional[btrfsprim.Key]{OK: true, Val: graphInfo.MinItem}, - MaxItem: containers.Optional[btrfsprim.Key]{OK: true, Val: graphInfo.MaxItem}, - }) - if err != nil { - panic(fmt.Errorf("should not happen: i/o error: %w", err)) - } - - ts.nodeCache.Add(laddr, ref) - - return ref } type rootStats struct { @@ -198,14 +158,14 @@ func (ts *RebuiltTrees) AddRoot(ctx context.Context, treeID btrfsprim.ObjID, roo if !roots.Has(rootNode) { continue } - for j, item := range ts.readNode(leaf).Data.BodyLeaf { + for j, item := range ts.keyIO.ReadNode(leaf).Data.BodyLeaf { if _, exists := tree.Items.Load(item.Key); exists { // This is a panic because I'm not really sure what the best way to // handle this is, and so if this happens I want the program to crash // and force me to figure out how to handle it. panic(fmt.Errorf("dup key=%v in tree=%v", item.Key, treeID)) } - tree.Items.Store(item.Key, itemPtr{ + tree.Items.Store(item.Key, keyio.ItemPtr{ Node: leaf, Idx: j, }) @@ -361,7 +321,7 @@ func (ts *RebuiltTrees) Load(ctx context.Context, treeID btrfsprim.ObjID, key bt if !ok { return nil, false } - return ts.readNode(ptr.Node).Data.BodyLeaf[ptr.Idx].Body, true + return ts.keyIO.ReadItem(ptr) } // Search searches for an item from a tree. @@ -372,7 +332,7 @@ func (ts *RebuiltTrees) Search(ctx context.Context, treeID btrfsprim.ObjID, fn f if !ts.AddTree(ctx, treeID) { return btrfsprim.Key{}, false } - k, _, ok := ts.trees[treeID].Items.Search(func(k btrfsprim.Key, _ itemPtr) int { + k, _, ok := ts.trees[treeID].Items.Search(func(k btrfsprim.Key, _ keyio.ItemPtr) int { return fn(k) }) return k, ok @@ -386,7 +346,7 @@ func (ts *RebuiltTrees) SearchAll(ctx context.Context, treeID btrfsprim.ObjID, f if !ts.AddTree(ctx, treeID) { return nil } - kvs := ts.trees[treeID].Items.SearchAll(func(k btrfsprim.Key, _ itemPtr) int { + kvs := ts.trees[treeID].Items.SearchAll(func(k btrfsprim.Key, _ keyio.ItemPtr) int { return fn(k) }) if len(kvs) == 0 { diff --git a/lib/btrfsprogs/btrfsinspect/rebuildnodes/keyio/keyio.go b/lib/btrfsprogs/btrfsinspect/rebuildnodes/keyio/keyio.go new file mode 100644 index 0000000..875b616 --- /dev/null +++ b/lib/btrfsprogs/btrfsinspect/rebuildnodes/keyio/keyio.go @@ -0,0 +1,117 @@ +// Copyright (C) 2022 Luke Shumaker <lukeshu@lukeshu.com> +// +// SPDX-License-Identifier: GPL-2.0-or-later + +package keyio + +import ( + "fmt" + + "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/btrfsprogs/btrfsinspect/rebuildnodes/graph" + "git.lukeshu.com/btrfs-progs-ng/lib/containers" + "git.lukeshu.com/btrfs-progs-ng/lib/diskio" +) + +type KeyAndTree struct { + btrfsprim.Key + TreeID btrfsprim.ObjID +} + +func (a KeyAndTree) Cmp(b KeyAndTree) int { + if d := a.Key.Cmp(b.Key); d != 0 { + return d + } + return containers.NativeCmp(a.TreeID, b.TreeID) +} + +type ItemPtr struct { + Node btrfsvol.LogicalAddr + Idx int +} + +func (ptr ItemPtr) String() string { + return fmt.Sprintf("node@%v[%v]", ptr.Node, ptr.Idx) +} + +type Handle struct { + Keys containers.SortedMap[KeyAndTree, ItemPtr] + + rawFile diskio.File[btrfsvol.LogicalAddr] + sb btrfstree.Superblock + graph *graph.Graph + + cache *containers.LRUCache[btrfsvol.LogicalAddr, *diskio.Ref[btrfsvol.LogicalAddr, btrfstree.Node]] +} + +func NewHandle(file diskio.File[btrfsvol.LogicalAddr], sb btrfstree.Superblock, graph *graph.Graph) *Handle { + return &Handle{ + rawFile: file, + sb: sb, + graph: graph, + + cache: containers.NewLRUCache[btrfsvol.LogicalAddr, *diskio.Ref[btrfsvol.LogicalAddr, btrfstree.Node]](8), + } +} + +func (o *Handle) InsertNode(nodeRef *diskio.Ref[btrfsvol.LogicalAddr, btrfstree.Node]) { + for i, item := range nodeRef.Data.BodyLeaf { + k := KeyAndTree{ + Key: item.Key, + TreeID: nodeRef.Data.Head.Owner, + } + if cur, ok := o.Keys.Load(k); !ok || o.graph.Nodes[cur.Node].Generation < nodeRef.Data.Head.Generation { + o.Keys.Store(k, ItemPtr{ + Node: nodeRef.Addr, + Idx: i, + }) + } + } +} + +func (o *Handle) ReadNode(laddr btrfsvol.LogicalAddr) *diskio.Ref[btrfsvol.LogicalAddr, btrfstree.Node] { + if cached, ok := o.cache.Get(laddr); ok { + return cached + } + + graphInfo, ok := o.graph.Nodes[laddr] + if !ok { + panic(fmt.Errorf("should not happen: node@%v is not mentioned in the in-memory graph", laddr)) + } + + ref, err := btrfstree.ReadNode(o.rawFile, o.sb, laddr, btrfstree.NodeExpectations{ + LAddr: containers.Optional[btrfsvol.LogicalAddr]{OK: true, Val: laddr}, + Level: containers.Optional[uint8]{OK: true, Val: graphInfo.Level}, + Generation: containers.Optional[btrfsprim.Generation]{OK: true, Val: graphInfo.Generation}, + Owner: func(treeID btrfsprim.ObjID) error { + if treeID != graphInfo.Owner { + return fmt.Errorf("expected owner=%v but claims to have owner=%v", + graphInfo.Owner, treeID) + } + return nil + }, + MinItem: containers.Optional[btrfsprim.Key]{OK: true, Val: graphInfo.MinItem}, + MaxItem: containers.Optional[btrfsprim.Key]{OK: true, Val: graphInfo.MaxItem}, + }) + if err != nil { + panic(fmt.Errorf("should not happen: i/o error: %w", err)) + } + + o.cache.Add(laddr, ref) + + return ref +} + +func (o *Handle) ReadItem(ptr ItemPtr) (item btrfsitem.Item, ok bool) { + if o.graph.Nodes[ptr.Node].Level != 0 || ptr.Idx < 0 { + return nil, false + } + items := o.ReadNode(ptr.Node).Data.BodyLeaf + if ptr.Idx >= len(items) { + return nil, false + } + return items[ptr.Idx].Body, true +} diff --git a/lib/btrfsprogs/btrfsinspect/rebuildnodes/orphans.go b/lib/btrfsprogs/btrfsinspect/rebuildnodes/orphans.go index 89e9ad4..517070d 100644 --- a/lib/btrfsprogs/btrfsinspect/rebuildnodes/orphans.go +++ b/lib/btrfsprogs/btrfsinspect/rebuildnodes/orphans.go @@ -11,7 +11,6 @@ import ( "github.com/datawire/dlib/dlog" - "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/btrfsprogs/btrfsinspect/rebuildnodes/graph" @@ -37,18 +36,6 @@ func _listRoots(ret containers.Set[btrfsvol.LogicalAddr], graph graph.Graph, lea } } -type keyAndTree struct { - btrfsprim.Key - TreeID btrfsprim.ObjID -} - -func (a keyAndTree) Cmp(b keyAndTree) int { - if d := a.Key.Cmp(b.Key); d != 0 { - return d - } - return containers.NativeCmp(a.TreeID, b.TreeID) -} - type crawlStats struct { DoneNodes int TotalNodes int @@ -61,20 +48,8 @@ func (s crawlStats) String() string { s.DoneNodes, s.TotalNodes, s.FoundLeafs) } -type readStats struct { - DoneLeafNodes int - TotalLeafNodes int -} - -func (s readStats) String() string { - return fmt.Sprintf("... reading leafs %v%% (%v/%v)", - int(100*float64(s.DoneLeafNodes)/float64(s.TotalLeafNodes)), - s.DoneLeafNodes, s.TotalLeafNodes) -} - func indexOrphans(ctx context.Context, fs diskio.File[btrfsvol.LogicalAddr], sb btrfstree.Superblock, graph graph.Graph) ( leaf2orphans map[btrfsvol.LogicalAddr]containers.Set[btrfsvol.LogicalAddr], - key2leaf *containers.SortedMap[keyAndTree, btrfsvol.LogicalAddr], err error, ) { @@ -99,36 +74,5 @@ func indexOrphans(ctx context.Context, fs diskio.File[btrfsvol.LogicalAddr], sb progress(len(graph.Nodes)) crawlProgressWriter.Done() - key2leaf = new(containers.SortedMap[keyAndTree, btrfsvol.LogicalAddr]) - readProgressWriter := textui.NewProgress[readStats](ctx, dlog.LogLevelInfo, 1*time.Second) - progress = func(done int) { - readProgressWriter.Set(readStats{ - DoneLeafNodes: done, - TotalLeafNodes: len(leaf2orphans), - }) - } - for i, laddr := range maps.SortedKeys(leaf2orphans) { - progress(i) - nodeRef, err := btrfstree.ReadNode[btrfsvol.LogicalAddr](fs, sb, laddr, btrfstree.NodeExpectations{ - LAddr: containers.Optional[btrfsvol.LogicalAddr]{OK: true, Val: laddr}, - Level: containers.Optional[uint8]{OK: true, Val: 0}, - }) - if err != nil { - return nil, nil, err - } - - for _, item := range nodeRef.Data.BodyLeaf { - k := keyAndTree{ - Key: item.Key, - TreeID: nodeRef.Data.Head.Owner, - } - if cur, ok := key2leaf.Load(k); !ok || graph.Nodes[cur].Generation < nodeRef.Data.Head.Generation { - key2leaf.Store(k, laddr) - } - } - } - progress(len(leaf2orphans)) - readProgressWriter.Done() - - return leaf2orphans, key2leaf, nil + return leaf2orphans, nil } diff --git a/lib/btrfsprogs/btrfsinspect/rebuildnodes/rebuild.go b/lib/btrfsprogs/btrfsinspect/rebuildnodes/rebuild.go index e0ca7a0..254cfee 100644 --- a/lib/btrfsprogs/btrfsinspect/rebuildnodes/rebuild.go +++ b/lib/btrfsprogs/btrfsinspect/rebuildnodes/rebuild.go @@ -20,6 +20,7 @@ import ( "git.lukeshu.com/btrfs-progs-ng/lib/btrfsprogs/btrfsinspect" "git.lukeshu.com/btrfs-progs-ng/lib/btrfsprogs/btrfsinspect/rebuildmappings" "git.lukeshu.com/btrfs-progs-ng/lib/btrfsprogs/btrfsinspect/rebuildnodes/graph" + "git.lukeshu.com/btrfs-progs-ng/lib/btrfsprogs/btrfsinspect/rebuildnodes/keyio" "git.lukeshu.com/btrfs-progs-ng/lib/btrfsprogs/btrfsinspect/rebuildnodes/uuidmap" "git.lukeshu.com/btrfs-progs-ng/lib/btrfsprogs/btrfsutil" "git.lukeshu.com/btrfs-progs-ng/lib/containers" @@ -38,7 +39,7 @@ type rebuilder struct { uuidMap uuidmap.UUIDMap csums containers.RBTree[containers.NativeOrdered[btrfsvol.LogicalAddr], btrfsinspect.SysExtentCSum] leaf2orphans map[btrfsvol.LogicalAddr]containers.Set[btrfsvol.LogicalAddr] - key2leaf containers.SortedMap[keyAndTree, btrfsvol.LogicalAddr] + keyIO keyio.Handle augments map[btrfsprim.ObjID]containers.Set[btrfsvol.LogicalAddr] @@ -64,7 +65,7 @@ func RebuildNodes(ctx context.Context, fs *btrfs.FS, nodeScanResults btrfsinspec } dlog.Info(ctx, "Indexing orphans...") - leaf2orphans, key2leaf, err := indexOrphans(ctx, fs, *sb, *scanData.nodeGraph) + leaf2orphans, err := indexOrphans(ctx, fs, *sb, *scanData.nodeGraph) if err != nil { return nil, err } @@ -79,7 +80,7 @@ func RebuildNodes(ctx context.Context, fs *btrfs.FS, nodeScanResults btrfsinspec uuidMap: *scanData.uuidMap, csums: *csums, leaf2orphans: leaf2orphans, - key2leaf: *key2leaf, + keyIO: *scanData.keyIO, augments: make(map[btrfsprim.ObjID]containers.Set[btrfsvol.LogicalAddr]), } @@ -335,10 +336,10 @@ func (o *rebuilder) want(ctx context.Context, treeID btrfsprim.ObjID, objID btrf ctx = dlog.WithField(ctx, "want_key", fmt.Sprintf("tree=%v key={%v %v ?}", treeID, objID, typ)) wants := make(containers.Set[btrfsvol.LogicalAddr]) - o.key2leaf.Subrange( - func(k keyAndTree, _ btrfsvol.LogicalAddr) int { k.Key.Offset = 0; return tgt.Cmp(k.Key) }, - func(_ keyAndTree, v btrfsvol.LogicalAddr) bool { - wants.InsertFrom(o.leaf2orphans[v]) + o.keyIO.Keys.Subrange( + func(k keyio.KeyAndTree, _ keyio.ItemPtr) int { k.Key.Offset = 0; return tgt.Cmp(k.Key) }, + func(_ keyio.KeyAndTree, v keyio.ItemPtr) bool { + wants.InsertFrom(o.leaf2orphans[v.Node]) return true }) o.wantAugment(ctx, treeID, wants) @@ -361,10 +362,10 @@ func (o *rebuilder) wantOff(ctx context.Context, treeID btrfsprim.ObjID, objID b ctx = dlog.WithField(ctx, "want_key", fmt.Sprintf("tree=%v key=%v", treeID, tgt)) wants := make(containers.Set[btrfsvol.LogicalAddr]) - o.key2leaf.Subrange( - func(k keyAndTree, _ btrfsvol.LogicalAddr) int { return tgt.Cmp(k.Key) }, - func(_ keyAndTree, v btrfsvol.LogicalAddr) bool { - wants.InsertFrom(o.leaf2orphans[v]) + o.keyIO.Keys.Subrange( + func(k keyio.KeyAndTree, _ keyio.ItemPtr) int { return tgt.Cmp(k.Key) }, + func(_ keyio.KeyAndTree, v keyio.ItemPtr) bool { + wants.InsertFrom(o.leaf2orphans[v.Node]) return true }) o.wantAugment(ctx, treeID, wants) @@ -392,20 +393,15 @@ func (o *rebuilder) wantFunc(ctx context.Context, treeID btrfsprim.ObjID, objID ctx = dlog.WithField(ctx, "want_key", fmt.Sprintf("tree=%v key=%v +func", treeID, tgt)) wants := make(containers.Set[btrfsvol.LogicalAddr]) - o.key2leaf.Subrange( - func(k keyAndTree, _ btrfsvol.LogicalAddr) int { k.Key.Offset = 0; return tgt.Cmp(k.Key) }, - func(k keyAndTree, v btrfsvol.LogicalAddr) bool { - nodeRef, err := btrfstree.ReadNode[btrfsvol.LogicalAddr](o.raw, o.sb, v, btrfstree.NodeExpectations{ - LAddr: containers.Optional[btrfsvol.LogicalAddr]{OK: true, Val: v}, - Generation: containers.Optional[btrfsprim.Generation]{OK: true, Val: o.graph.Nodes[v].Generation}, - }) - if err != nil { - o.ioErr(ctx, err) + o.keyIO.Keys.Subrange( + func(k keyio.KeyAndTree, _ keyio.ItemPtr) int { k.Key.Offset = 0; return tgt.Cmp(k.Key) }, + func(k keyio.KeyAndTree, v keyio.ItemPtr) bool { + itemBody, ok := o.keyIO.ReadItem(v) + if !ok { + o.ioErr(ctx, fmt.Errorf("could not read previously read item: %v", v)) } - for _, item := range nodeRef.Data.BodyLeaf { - if k.Key == item.Key && fn(item.Body) { - wants.InsertFrom(o.leaf2orphans[v]) - } + if fn(itemBody) { + wants.InsertFrom(o.leaf2orphans[v.Node]) } return true }) @@ -441,18 +437,18 @@ func (o *rebuilder) wantCSum(ctx context.Context, beg, end btrfsvol.LogicalAddr) continue } run := rbNode.Value.Sums - key := keyAndTree{ + key := keyio.KeyAndTree{ Key: rbNode.Value.Key, TreeID: btrfsprim.CSUM_TREE_OBJECTID, } - leaf, ok := o.key2leaf.Load(key) + itemPtr, ok := o.keyIO.Keys.Load(key) if !ok { // This is a panic because if we found it in `o.csums` then it has // to be in some Node, and if we didn't find it from // btrfs.LookupCSum(), then that Node must be an orphan. panic(fmt.Errorf("should not happen: no orphan contains %v", key.Key)) } - o.wantAugment(ctx, key.TreeID, o.leaf2orphans[leaf]) + o.wantAugment(ctx, key.TreeID, o.leaf2orphans[itemPtr.Node]) beg = run.Addr.Add(run.Size()) } @@ -558,8 +554,8 @@ func (o *rebuilder) wantFileExt(ctx context.Context, treeID btrfsprim.ObjID, ino } ctx := dlog.WithField(ctx, "want_key", fmt.Sprintf("file extent for tree=%v inode=%v bytes [%v, %v)", treeID, ino, gap.Beg, gap.End)) wants := make(containers.Set[btrfsvol.LogicalAddr]) - o.key2leaf.Subrange( - func(k keyAndTree, _ btrfsvol.LogicalAddr) int { + o.keyIO.Keys.Subrange( + func(k keyio.KeyAndTree, _ keyio.ItemPtr) int { switch { case min.Cmp(k.Key) < 0: return 1 @@ -569,45 +565,37 @@ func (o *rebuilder) wantFileExt(ctx context.Context, treeID btrfsprim.ObjID, ino return 0 } }, - func(k keyAndTree, v btrfsvol.LogicalAddr) bool { - nodeRef, err := btrfstree.ReadNode[btrfsvol.LogicalAddr](o.raw, o.sb, v, btrfstree.NodeExpectations{ - LAddr: containers.Optional[btrfsvol.LogicalAddr]{OK: true, Val: v}, - Generation: containers.Optional[btrfsprim.Generation]{OK: true, Val: o.graph.Nodes[v].Generation}, - }) - if err != nil { - o.ioErr(ctx, fmt.Errorf("error reading previously read node@%v: %w", v, err)) + func(k keyio.KeyAndTree, v keyio.ItemPtr) bool { + itemBody, ok := o.keyIO.ReadItem(v) + if !ok { + o.ioErr(ctx, fmt.Errorf("could not read previously read item: %v", v)) } - for _, item := range nodeRef.Data.BodyLeaf { - if k.Key != item.Key { - continue + switch itemBody := itemBody.(type) { + case btrfsitem.FileExtent: + itemBeg := int64(k.Offset) + itemSize, err := itemBody.Size() + if err != nil { + o.fsErr(ctx, fmt.Errorf("FileExtent: tree=%v key=%v: %w", treeID, k, err)) + break } - switch itemBody := item.Body.(type) { - case btrfsitem.FileExtent: - itemBeg := int64(item.Key.Offset) - itemSize, err := itemBody.Size() - if err != nil { - o.fsErr(ctx, fmt.Errorf("FileExtent: tree=%v key=%v: %w", treeID, item.Key, err)) - continue - } - itemEnd := itemBeg + itemSize - // We're being greedy and "wanting" any extent that has any overlap with - // the gap. But maybe instead we sould only want extents that are - // *entirely* within the gap. I'll have to run it on real filesystems - // to see what works better. - // - // TODO(lukeshu): Re-evaluate whether being greedy here is the right - // thing. - if itemEnd > gap.Beg && itemBeg < gap.End { - wants.InsertFrom(o.leaf2orphans[v]) - } - case btrfsitem.Error: - o.fsErr(ctx, fmt.Errorf("error decoding item: tree=%v key=%v: %w", treeID, item.Key, itemBody.Err)) - default: - // This is a panic because the item decoder should not emit EXTENT_DATA - // items as anything but btrfsitem.FileExtent or btrfsitem.Error without - // this code also being updated. - panic(fmt.Errorf("should not happen: EXTENT_DATA item has unexpected type: %T", itemBody)) + itemEnd := itemBeg + itemSize + // We're being greedy and "wanting" any extent that has any overlap with + // the gap. But maybe instead we sould only want extents that are + // *entirely* within the gap. I'll have to run it on real filesystems + // to see what works better. + // + // TODO(lukeshu): Re-evaluate whether being greedy here is the right + // thing. + if itemEnd > gap.Beg && itemBeg < gap.End { + wants.InsertFrom(o.leaf2orphans[v.Node]) } + case btrfsitem.Error: + o.fsErr(ctx, fmt.Errorf("error decoding item: tree=%v key=%v: %w", treeID, k, itemBody.Err)) + default: + // This is a panic because the item decoder should not emit EXTENT_DATA + // items as anything but btrfsitem.FileExtent or btrfsitem.Error without + // this code also being updated. + panic(fmt.Errorf("should not happen: EXTENT_DATA item has unexpected type: %T", itemBody)) } return true }) diff --git a/lib/btrfsprogs/btrfsinspect/rebuildnodes/scan.go b/lib/btrfsprogs/btrfsinspect/rebuildnodes/scan.go index 3575534..7e01693 100644 --- a/lib/btrfsprogs/btrfsinspect/rebuildnodes/scan.go +++ b/lib/btrfsprogs/btrfsinspect/rebuildnodes/scan.go @@ -16,6 +16,7 @@ import ( "git.lukeshu.com/btrfs-progs-ng/lib/btrfs/btrfsvol" "git.lukeshu.com/btrfs-progs-ng/lib/btrfsprogs/btrfsinspect" "git.lukeshu.com/btrfs-progs-ng/lib/btrfsprogs/btrfsinspect/rebuildnodes/graph" + "git.lukeshu.com/btrfs-progs-ng/lib/btrfsprogs/btrfsinspect/rebuildnodes/keyio" "git.lukeshu.com/btrfs-progs-ng/lib/btrfsprogs/btrfsinspect/rebuildnodes/uuidmap" "git.lukeshu.com/btrfs-progs-ng/lib/containers" "git.lukeshu.com/btrfs-progs-ng/lib/maps" @@ -25,6 +26,7 @@ import ( type scanResult struct { uuidMap *uuidmap.UUIDMap nodeGraph *graph.Graph + keyIO *keyio.Handle } type scanStats struct { @@ -56,6 +58,7 @@ func ScanDevices(ctx context.Context, fs *btrfs.FS, scanResults btrfsinspect.Sca uuidMap: uuidmap.New(), nodeGraph: graph.New(*sb), } + ret.keyIO = keyio.NewHandle(fs, *sb, ret.nodeGraph) progress(done, total) for _, devResults := range scanResults { @@ -72,6 +75,7 @@ func ScanDevices(ctx context.Context, fs *btrfs.FS, scanResults btrfsinspect.Sca } ret.nodeGraph.InsertNode(nodeRef) + ret.keyIO.InsertNode(nodeRef) done++ progress(done, total) |