diff options
4 files changed, 103 insertions, 82 deletions
diff --git a/lib/btrfsprogs/btrfsinspect/rebuildnodes/btrees/rebuilt_btrees.go b/lib/btrfsprogs/btrfsinspect/rebuildnodes/btrees/rebuilt_btrees.go index f919b37..50c75a4 100644 --- a/lib/btrfsprogs/btrfsinspect/rebuildnodes/btrees/rebuilt_btrees.go +++ b/lib/btrfsprogs/btrfsinspect/rebuildnodes/btrees/rebuilt_btrees.go @@ -32,6 +32,7 @@ type rebuiltTree struct { // all leafs (lvl=0) that pass .isOwnerOK, even if not in the tree leafToRoots map[btrfsvol.LogicalAddr]containers.Set[btrfsvol.LogicalAddr] + keys containers.SortedMap[btrfsprim.Key, keyio.ItemPtr] // mutable Roots containers.Set[btrfsvol.LogicalAddr] @@ -41,14 +42,14 @@ type rebuiltTree struct { // isOwnerOK returns whether it is permissible for a node with // .Head.Owner=owner to be in this tree. -func (tree *rebuiltTree) isOwnerOK(owner btrfsprim.ObjID) bool { +func (tree *rebuiltTree) isOwnerOK(owner btrfsprim.ObjID, gen btrfsprim.Generation) bool { for { - if tree == nil { - return false - } if owner == tree.ID { return true } + if tree.Parent == nil || gen >= tree.ParentGen { + return false + } tree = tree.Parent } } @@ -68,6 +69,38 @@ func (tree *rebuiltTree) cowDistance(parentID btrfsprim.ObjID) (dist int, ok boo } } +func (tree *rebuiltTree) shouldReplace(graph pkggraph.Graph, oldNode, newNode btrfsvol.LogicalAddr) bool { + oldDist, _ := tree.cowDistance(graph.Nodes[oldNode].Owner) + newDist, _ := tree.cowDistance(graph.Nodes[newNode].Owner) + switch { + case newDist < oldDist: + // Replace the old one with the new lower-dist one. + return true + case newDist > oldDist: + // Retain the old lower-dist one. + return false + default: + oldGen := graph.Nodes[oldNode].Generation + newGen := graph.Nodes[newNode].Generation + switch { + case newGen > oldGen: + // Replace the old one with the new higher-gen one. + return true + case newGen < oldGen: + // Retain the old higher-gen one. + return false + default: + // 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 nodes in tree=%v: old=%v=%v ; new=%v=%v", + tree.ID, + oldNode, graph.Nodes[oldNode], + newNode, graph.Nodes[newNode])) + } + } +} + // RebuiltTrees is an abstraction for rebuilding and accessing // potentially broken btrees. // @@ -189,24 +222,9 @@ func (ts *RebuiltTrees) AddRoot(ctx context.Context, treeID btrfsprim.ObjID, roo if oldPtr, exists := tree.Items.Load(itemKey); !exists { tree.Items.Store(itemKey, newPtr) numAdded++ - } else { - oldGen := ts.graph.Nodes[oldPtr.Node].Generation - newGen := ts.graph.Nodes[newPtr.Node].Generation - switch { - case oldGen < newGen: - tree.Items.Store(itemKey, newPtr) - numReplaced++ - case oldGen > newGen: - // keep the old one - case oldGen == newGen: - // 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: old=%v=%#v ; new=%v=%#v", - itemKey, treeID, - oldPtr, ts.graph.Nodes[oldPtr.Node], - newPtr, ts.graph.Nodes[newPtr.Node])) - } + } else if tree.shouldReplace(ts.graph, oldPtr.Node, newPtr.Node) { + tree.Items.Store(itemKey, newPtr) + numReplaced++ } ts.cbAddedItem(ctx, treeID, itemKey) progress(i) @@ -327,26 +345,42 @@ func (tree *rebuiltTree) indexNode(graph pkggraph.Graph, node btrfsvol.LogicalAd return } if slices.Contains(node, stack) { - return + panic("loop") } - if !tree.isOwnerOK(graph.Nodes[node].Owner) { + if !tree.isOwnerOK(graph.Nodes[node].Owner, graph.Nodes[node].Generation) { index[node] = nil return } + + // tree.leafToRoots + stack = append(stack, node) + var roots containers.Set[btrfsvol.LogicalAddr] kps := slices.RemoveAllFunc(graph.EdgesTo[node], func(kp *pkggraph.Edge) bool { - return !tree.isOwnerOK(graph.Nodes[kp.FromNode].Owner) + return !tree.isOwnerOK(graph.Nodes[kp.FromNode].Owner, graph.Nodes[kp.FromNode].Generation) }) - if len(kps) == 0 { - index[node] = containers.NewSet[btrfsvol.LogicalAddr](node) - return - } - stack = append(stack, node) - roots := make(containers.Set[btrfsvol.LogicalAddr]) for _, kp := range kps { tree.indexNode(graph, kp.FromNode, index, progress, stack) - roots.InsertFrom(index[kp.FromNode]) + if len(index[kp.FromNode]) > 0 { + if roots == nil { + roots = make(containers.Set[btrfsvol.LogicalAddr]) + } + roots.InsertFrom(index[kp.FromNode]) + } + } + if roots == nil { + roots = containers.NewSet[btrfsvol.LogicalAddr](node) } index[node] = roots + + // tree.keys + for i, key := range graph.Nodes[node].Items { + if oldPtr, ok := tree.keys.Load(key); !ok || tree.shouldReplace(graph, oldPtr.Node, node) { + tree.keys.Store(key, keyio.ItemPtr{ + Node: node, + Idx: i, + }) + } + } } // Load reads an item from a tree. @@ -426,6 +460,14 @@ func (ts *RebuiltTrees) LeafToRoots(ctx context.Context, treeID btrfsprim.ObjID, return ret } +// Keys returns a map of all keys in node that would be valid in this tree. +// +// It is invalid (panic) to call Keys for a tree without having called +// AddTree first. +func (ts *RebuiltTrees) Keys(treeID btrfsprim.ObjID) *containers.SortedMap[btrfsprim.Key, keyio.ItemPtr] { + return &ts.trees[treeID].keys +} + // COWDistance returns how many COW-snapshots down from the 'child' // tree is from the 'parent' tree. // diff --git a/lib/btrfsprogs/btrfsinspect/rebuildnodes/keyio/keyio.go b/lib/btrfsprogs/btrfsinspect/rebuildnodes/keyio/keyio.go index 875b616..5ae9ce2 100644 --- a/lib/btrfsprogs/btrfsinspect/rebuildnodes/keyio/keyio.go +++ b/lib/btrfsprogs/btrfsinspect/rebuildnodes/keyio/keyio.go @@ -38,16 +38,14 @@ func (ptr ItemPtr) String() string { } type Handle struct { - Keys containers.SortedMap[KeyAndTree, ItemPtr] - rawFile diskio.File[btrfsvol.LogicalAddr] sb btrfstree.Superblock - graph *graph.Graph + 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 { +func NewHandle(file diskio.File[btrfsvol.LogicalAddr], sb btrfstree.Superblock, graph graph.Graph) *Handle { return &Handle{ rawFile: file, sb: sb, @@ -57,21 +55,6 @@ func NewHandle(file diskio.File[btrfsvol.LogicalAddr], sb btrfstree.Superblock, } } -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 diff --git a/lib/btrfsprogs/btrfsinspect/rebuildnodes/rebuild.go b/lib/btrfsprogs/btrfsinspect/rebuildnodes/rebuild.go index fecf5e6..982c27d 100644 --- a/lib/btrfsprogs/btrfsinspect/rebuildnodes/rebuild.go +++ b/lib/btrfsprogs/btrfsinspect/rebuildnodes/rebuild.go @@ -42,7 +42,7 @@ type rebuilder struct { } func RebuildNodes(ctx context.Context, fs *btrfs.FS, nodeScanResults btrfsinspect.ScanDevicesResult) (map[btrfsprim.ObjID]containers.Set[btrfsvol.LogicalAddr], error) { - nodeGraph, keyIO, err := ScanDevices(ctx, fs, nodeScanResults) // ScanDevices does its own logging + nodeGraph, err := ScanDevices(ctx, fs, nodeScanResults) // ScanDevices does its own logging if err != nil { return nil, err } @@ -60,6 +60,7 @@ func RebuildNodes(ctx context.Context, fs *btrfs.FS, nodeScanResults btrfsinspec } dlog.Info(ctx, "Rebuilding node tree...") + keyIO := keyio.NewHandle(fs, *sb, nodeGraph) o := &rebuilder{ sb: *sb, @@ -402,9 +403,9 @@ func (o *rebuilder) _want(ctx context.Context, treeID btrfsprim.ObjID, objID btr ctx = dlog.WithField(ctx, "want_key", fmt.Sprintf("tree=%v key={%v %v ?}", treeID, objID, typ)) wants := make(containers.Set[btrfsvol.LogicalAddr]) - 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 { + o.rebuilt.Keys(treeID).Subrange( + func(k btrfsprim.Key, _ keyio.ItemPtr) int { k.Offset = 0; return tgt.Cmp(k) }, + func(_ btrfsprim.Key, v keyio.ItemPtr) bool { wants.InsertFrom(o.rebuilt.LeafToRoots(ctx, treeID, v.Node)) return true }) @@ -437,9 +438,9 @@ func (o *rebuilder) _wantOff(ctx context.Context, treeID btrfsprim.ObjID, objID ctx = dlog.WithField(ctx, "want_key", fmt.Sprintf("tree=%v key=%v", treeID, tgt)) wants := make(containers.Set[btrfsvol.LogicalAddr]) - o.keyIO.Keys.Subrange( - func(k keyio.KeyAndTree, _ keyio.ItemPtr) int { return tgt.Cmp(k.Key) }, - func(_ keyio.KeyAndTree, v keyio.ItemPtr) bool { + o.rebuilt.Keys(treeID).Subrange( + func(k btrfsprim.Key, _ keyio.ItemPtr) int { return tgt.Cmp(k) }, + func(_ btrfsprim.Key, v keyio.ItemPtr) bool { wants.InsertFrom(o.rebuilt.LeafToRoots(ctx, treeID, v.Node)) return true }) @@ -478,9 +479,9 @@ 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.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 { + o.rebuilt.Keys(treeID).Subrange( + func(k btrfsprim.Key, _ keyio.ItemPtr) int { k.Offset = 0; return tgt.Cmp(k) }, + func(k btrfsprim.Key, v keyio.ItemPtr) bool { itemBody, ok := o.keyIO.ReadItem(v) if !ok { o.ioErr(ctx, fmt.Errorf("could not read previously read item: %v at %v", k, v)) @@ -523,24 +524,22 @@ func (o *rebuilder) wantCSum(ctx context.Context, beg, end btrfsvol.LogicalAddr) continue } run := rbNode.Value.Sums - key := keyio.KeyAndTree{ - Key: rbNode.Value.Key, - TreeID: btrfsprim.CSUM_TREE_OBJECTID, - } + key := rbNode.Value.Key + treeID := btrfsprim.CSUM_TREE_OBJECTID // Check if we already have it. // .Search is more efficient than .Load, because it doesn't load the body (and we don't need the body). - if _, ok := o.rebuilt.Search(ctx, key.TreeID, key.Key.Cmp); !ok { + if _, ok := o.rebuilt.Search(ctx, treeID, key.Cmp); !ok { // We need to insert it. - itemPtr, ok := o.keyIO.Keys.Load(key) + itemPtr, ok := o.rebuilt.Keys(btrfsprim.CSUM_TREE_OBJECTID).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)) + panic(fmt.Errorf("should not happen: no orphan contains %v", key)) } - o.wantAugment(ctx, key.TreeID, o.rebuilt.LeafToRoots(ctx, key.TreeID, itemPtr.Node)) + o.wantAugment(ctx, treeID, o.rebuilt.LeafToRoots(ctx, treeID, itemPtr.Node)) } beg = run.Addr.Add(run.Size()) @@ -656,18 +655,18 @@ 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.keyIO.Keys.Subrange( - func(k keyio.KeyAndTree, _ keyio.ItemPtr) int { + o.rebuilt.Keys(treeID).Subrange( + func(k btrfsprim.Key, _ keyio.ItemPtr) int { switch { - case min.Cmp(k.Key) < 0: + case min.Cmp(k) < 0: return 1 - case max.Cmp(k.Key) > 0: + case max.Cmp(k) > 0: return -1 default: return 0 } }, - func(k keyio.KeyAndTree, v keyio.ItemPtr) bool { + func(k btrfsprim.Key, 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)) diff --git a/lib/btrfsprogs/btrfsinspect/rebuildnodes/scan.go b/lib/btrfsprogs/btrfsinspect/rebuildnodes/scan.go index 93d3e0c..bcf2f5b 100644 --- a/lib/btrfsprogs/btrfsinspect/rebuildnodes/scan.go +++ b/lib/btrfsprogs/btrfsinspect/rebuildnodes/scan.go @@ -16,7 +16,6 @@ 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/containers" "git.lukeshu.com/btrfs-progs-ng/lib/textui" ) @@ -31,12 +30,12 @@ func (s scanStats) String() string { s.N, s.D) } -func ScanDevices(ctx context.Context, fs *btrfs.FS, scanResults btrfsinspect.ScanDevicesResult) (graph.Graph, *keyio.Handle, error) { +func ScanDevices(ctx context.Context, fs *btrfs.FS, scanResults btrfsinspect.ScanDevicesResult) (graph.Graph, error) { dlog.Infof(ctx, "Reading node data from FS...") sb, err := fs.Superblock() if err != nil { - return graph.Graph{}, nil, err + return graph.Graph{}, err } total := countNodes(scanResults) @@ -47,7 +46,6 @@ func ScanDevices(ctx context.Context, fs *btrfs.FS, scanResults btrfsinspect.Sca } nodeGraph := graph.New(*sb) - keyIO := keyio.NewHandle(fs, *sb, nodeGraph) progress(done, total) for _, devResults := range scanResults { @@ -56,11 +54,10 @@ func ScanDevices(ctx context.Context, fs *btrfs.FS, scanResults btrfsinspect.Sca LAddr: containers.Optional[btrfsvol.LogicalAddr]{OK: true, Val: laddr}, }) if err != nil { - return graph.Graph{}, nil, err + return graph.Graph{}, err } nodeGraph.InsertNode(nodeRef) - keyIO.InsertNode(nodeRef) done++ progress(done, total) @@ -75,10 +72,10 @@ func ScanDevices(ctx context.Context, fs *btrfs.FS, scanResults btrfsinspect.Sca progressWriter = textui.NewProgress[scanStats](ctx, dlog.LogLevelInfo, 1*time.Second) dlog.Infof(ctx, "Checking keypointers for dead-ends...") if err := nodeGraph.FinalCheck(fs, *sb, progress); err != nil { - return graph.Graph{}, nil, err + return graph.Graph{}, err } progressWriter.Done() dlog.Info(ctx, "... done checking keypointers") - return *nodeGraph, keyIO, nil + return *nodeGraph, nil } |