From 525adfb185a0a73f38f9c0acaa748f5ebd825e1f Mon Sep 17 00:00:00 2001 From: Luke Shumaker Date: Sat, 17 Sep 2022 20:40:36 -0600 Subject: flatten visualizenodes, comment out rebuildnodes --- cmd/btrfs-rec/inspect_rebuildnodes.go | 2 + .../btrfsinspect/rebuildnodes/bak_rebuildnodes.go | 102 +++++++++ .../btrfsinspect/rebuildnodes/bak_rebuilttrees.go | 89 ++++++++ .../btrfsinspect/rebuildnodes/bak_s3_reinit.go | 139 ++++++++++++ .../rebuildnodes/bak_s3_reinit_test.go | 82 +++++++ .../btrfsinspect/rebuildnodes/bak_s4_reattach.go | 161 +++++++++++++ .../btrfsinspect/rebuildnodes/rebuildnodes.go | 117 ---------- .../btrfsinspect/rebuildnodes/rebuilttrees.go | 87 ------- .../btrfsinspect/rebuildnodes/s1_uuidmap.go | 20 -- .../btrfsinspect/rebuildnodes/s2_classify.go | 141 ------------ .../btrfsinspect/rebuildnodes/s3_reinit.go | 142 ------------ .../btrfsinspect/rebuildnodes/s3_reinit_test.go | 80 ------- .../btrfsinspect/rebuildnodes/s4_reattach.go | 159 ------------- lib/btrfsprogs/btrfsinspect/rebuildnodes/scan.go | 100 ++++++-- .../btrfsinspect/rebuildnodes/treeancestors.go | 25 ++ lib/btrfsprogs/btrfsinspect/rebuildnodes/util.go | 4 +- .../btrfsinspect/rebuildnodes/visualizenodes.go | 252 ++++++++++----------- 17 files changed, 808 insertions(+), 894 deletions(-) create mode 100644 lib/btrfsprogs/btrfsinspect/rebuildnodes/bak_rebuildnodes.go create mode 100644 lib/btrfsprogs/btrfsinspect/rebuildnodes/bak_rebuilttrees.go create mode 100644 lib/btrfsprogs/btrfsinspect/rebuildnodes/bak_s3_reinit.go create mode 100644 lib/btrfsprogs/btrfsinspect/rebuildnodes/bak_s3_reinit_test.go create mode 100644 lib/btrfsprogs/btrfsinspect/rebuildnodes/bak_s4_reattach.go delete mode 100644 lib/btrfsprogs/btrfsinspect/rebuildnodes/rebuildnodes.go delete mode 100644 lib/btrfsprogs/btrfsinspect/rebuildnodes/rebuilttrees.go delete mode 100644 lib/btrfsprogs/btrfsinspect/rebuildnodes/s1_uuidmap.go delete mode 100644 lib/btrfsprogs/btrfsinspect/rebuildnodes/s2_classify.go delete mode 100644 lib/btrfsprogs/btrfsinspect/rebuildnodes/s3_reinit.go delete mode 100644 lib/btrfsprogs/btrfsinspect/rebuildnodes/s3_reinit_test.go delete mode 100644 lib/btrfsprogs/btrfsinspect/rebuildnodes/s4_reattach.go create mode 100644 lib/btrfsprogs/btrfsinspect/rebuildnodes/treeancestors.go diff --git a/cmd/btrfs-rec/inspect_rebuildnodes.go b/cmd/btrfs-rec/inspect_rebuildnodes.go index 36a9207..5d0a54e 100644 --- a/cmd/btrfs-rec/inspect_rebuildnodes.go +++ b/cmd/btrfs-rec/inspect_rebuildnodes.go @@ -4,6 +4,7 @@ package main +/* import ( "bufio" "io" @@ -65,3 +66,4 @@ func writeNodesJSON(w io.Writer, rebuiltNodes map[btrfsvol.LogicalAddr]*rebuildn ForceTrailingNewlines: true, }, rebuiltNodes) } +*/ diff --git a/lib/btrfsprogs/btrfsinspect/rebuildnodes/bak_rebuildnodes.go b/lib/btrfsprogs/btrfsinspect/rebuildnodes/bak_rebuildnodes.go new file mode 100644 index 0000000..1a9f487 --- /dev/null +++ b/lib/btrfsprogs/btrfsinspect/rebuildnodes/bak_rebuildnodes.go @@ -0,0 +1,102 @@ +// Copyright (C) 2022 Luke Shumaker +// +// SPDX-License-Identifier: GPL-2.0-or-later + +package rebuildnodes + +/* +import ( + "context" + "errors" + + "git.lukeshu.com/btrfs-progs-ng/lib/btrfs" + "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" + "git.lukeshu.com/btrfs-progs-ng/lib/btrfsprogs/btrfsutil" + "git.lukeshu.com/btrfs-progs-ng/lib/diskio" +) + +func RebuildNodes(ctx context.Context, fs *btrfs.FS, nodeScanResults btrfsinspect.ScanDevicesResult) (map[btrfsvol.LogicalAddr]*RebuiltNode, error) { + uuidMap, err := buildUUIDMap(ctx, fs, nodeScanResults) + if err != nil { + return nil, err + } + + nfs := &RebuiltTrees{ + inner: fs, + uuidMap: uuidMap, + } + + orphanedNodes, badNodes, treeAncestors, err := classifyNodes(ctx, nfs, nodeScanResults) + if err != nil { + return nil, err + } + + uuidMap.considerAncestors(ctx, treeAncestors) + + rebuiltNodes, err := reInitBrokenNodes(ctx, nfs, badNodes) + if err != nil { + return nil, err + } + + if err := reAttachNodes(ctx, nfs, orphanedNodes, rebuiltNodes); err != nil { + return nil, err + } + + return rebuiltNodes, nil +} + +func spanOfTreePath(fs _FS, path btrfstree.TreePath) (btrfsprim.Key, btrfsprim.Key) { + // tree root error + if len(path) == 0 { + return btrfsprim.Key{}, maxKey + } + + // item error + if path.Node(-1).ToNodeAddr == 0 { + // If we got an item error, then the node is readable + node, _ := fs.ReadNode(path.Parent()) + key := node.Data.BodyLeaf[path.Node(-1).FromItemIdx].Key + return key, key + } + + // node error + // + // assume that path.Node(-1).ToNodeAddr is not readable, but that path.Node(-2).ToNodeAddr is. + if len(path) == 1 { + return btrfsprim.Key{}, maxKey + } + parentNode, _ := fs.ReadNode(path.Parent()) + low := parentNode.Data.BodyInternal[path.Node(-1).FromItemIdx].Key + var high btrfsprim.Key + if path.Node(-1).FromItemIdx+1 < len(parentNode.Data.BodyInternal) { + high = keyMm(parentNode.Data.BodyInternal[path.Node(-1).FromItemIdx+1].Key) + } else { + parentPath := path.Parent().DeepCopy() + _, high = spanOfTreePath(fs, parentPath) + } + return low, high +} + +func getChunkTreeUUID(ctx context.Context, fs _FS) (btrfsprim.UUID, bool) { + ctx, cancel := context.WithCancel(ctx) + var ret btrfsprim.UUID + var retOK bool + btrfsutil.WalkAllTrees(ctx, fs, btrfsutil.WalkAllTreesHandler{ + TreeWalkHandler: btrfstree.TreeWalkHandler{ + Node: func(path btrfstree.TreePath, node *diskio.Ref[btrfsvol.LogicalAddr, btrfstree.Node]) error { + ret = node.Data.Head.ChunkTreeUUID + retOK = true + cancel() + return nil + }, + }, + Err: func(err *btrfsutil.WalkError) { + // do nothing + }, + }) + return ret, retOK +} +*/ diff --git a/lib/btrfsprogs/btrfsinspect/rebuildnodes/bak_rebuilttrees.go b/lib/btrfsprogs/btrfsinspect/rebuildnodes/bak_rebuilttrees.go new file mode 100644 index 0000000..7e1a7e9 --- /dev/null +++ b/lib/btrfsprogs/btrfsinspect/rebuildnodes/bak_rebuilttrees.go @@ -0,0 +1,89 @@ +// Copyright (C) 2022 Luke Shumaker +// +// SPDX-License-Identifier: GPL-2.0-or-later + +package rebuildnodes + +/* +import ( + "context" + "fmt" + + "git.lukeshu.com/btrfs-progs-ng/lib/btrfs" + "git.lukeshu.com/btrfs-progs-ng/lib/btrfs/btrfsprim" + "git.lukeshu.com/btrfs-progs-ng/lib/btrfs/btrfstree" + "git.lukeshu.com/btrfs-progs-ng/lib/btrfs/btrfsvol" + "git.lukeshu.com/btrfs-progs-ng/lib/diskio" +) + +type RebuiltTrees struct { + inner *btrfs.FS + uuidMap uuidMap + nodes map[btrfsvol.LogicalAddr]*RebuiltNode +} + +type _FS interface { + diskio.File[btrfsvol.LogicalAddr] + btrfstree.NodeFile + btrfstree.NodeSource + btrfstree.TreeOperator +} + +// diskio.File + +func (fs *RebuiltTrees) Name() string { return fs.inner.Name() } +func (fs *RebuiltTrees) Size() btrfsvol.LogicalAddr { return fs.inner.Size() } +func (fs *RebuiltTrees) Close() error { return fs.inner.Close() } +func (fs *RebuiltTrees) ReadAt(p []byte, off btrfsvol.LogicalAddr) (int, error) { + sb, err := fs.Superblock() + if err != nil { + return 0, err + } + if rebuilt, ok := fs.nodes[off]; ok && len(p) == int(sb.NodeSize) { + rebuilt.Node.Head.Checksum, err = rebuilt.Node.CalculateChecksum() + if err != nil { + panic(fmt.Errorf("should not happen: %w", err)) + } + bs, err := rebuilt.Node.MarshalBinary() + if err != nil { + panic(fmt.Errorf("should not happen: %w", err)) + } + if len(p) != len(bs) { + panic(fmt.Errorf("should not happen: sb.NodeSize=%v but node marshaled to %v", sb.NodeSize, len(bs))) + } + return copy(p, bs), nil + } + return fs.inner.ReadAt(p, off) +} +func (fs *RebuiltTrees) WriteAt(p []byte, off btrfsvol.LogicalAddr) (int, error) { + return fs.inner.WriteAt(p, off) +} + +// btrfstree.NodeFile + +func (fs *RebuiltTrees) ParentTree(tree btrfsprim.ObjID) (btrfsprim.ObjID, bool) { + return fs.uuidMap.ParentTree(tree) +} + +// btrfstree.NodeSource + +func (fs *RebuiltTrees) Superblock() (*btrfstree.Superblock, error) { return fs.inner.Superblock() } +func (fs *RebuiltTrees) ReadNode(path btrfstree.TreePath) (*diskio.Ref[btrfsvol.LogicalAddr, btrfstree.Node], error) { + return btrfstree.FSReadNode(fs, path) +} + +// btrfstree.TreeOperator + +func (fs *RebuiltTrees) TreeWalk(ctx context.Context, treeID btrfsprim.ObjID, errHandle func(*btrfstree.TreeError), cbs btrfstree.TreeWalkHandler) { + btrfstree.TreeOperatorImpl{NodeSource: fs}.TreeWalk(ctx, treeID, errHandle, cbs) +} +func (fs *RebuiltTrees) TreeLookup(treeID btrfsprim.ObjID, key btrfsprim.Key) (btrfstree.Item, error) { + return btrfstree.TreeOperatorImpl{NodeSource: fs}.TreeLookup(treeID, key) +} +func (fs *RebuiltTrees) TreeSearch(treeID btrfsprim.ObjID, fn func(key btrfsprim.Key, size uint32) int) (btrfstree.Item, error) { + return btrfstree.TreeOperatorImpl{NodeSource: fs}.TreeSearch(treeID, fn) +} +func (fs *RebuiltTrees) TreeSearchAll(treeID btrfsprim.ObjID, fn func(key btrfsprim.Key, size uint32) int) ([]btrfstree.Item, error) { + return btrfstree.TreeOperatorImpl{NodeSource: fs}.TreeSearchAll(treeID, fn) +} +*/ diff --git a/lib/btrfsprogs/btrfsinspect/rebuildnodes/bak_s3_reinit.go b/lib/btrfsprogs/btrfsinspect/rebuildnodes/bak_s3_reinit.go new file mode 100644 index 0000000..5983e2f --- /dev/null +++ b/lib/btrfsprogs/btrfsinspect/rebuildnodes/bak_s3_reinit.go @@ -0,0 +1,139 @@ +// Copyright (C) 2022 Luke Shumaker +// +// SPDX-License-Identifier: GPL-2.0-or-later + +package rebuildnodes + +/* +import ( + "fmt" + "reflect" + + "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/containers" + "git.lukeshu.com/btrfs-progs-ng/lib/slices" +) + +type RebuiltNode struct { + Errs containers.Set[string] + MinKey, MaxKey btrfsprim.Key + InTrees containers.Set[btrfsprim.ObjID] + btrfstree.Node +} + +func (a RebuiltNode) Compat(b RebuiltNode) bool { + a.Node.Head.Generation = b.Node.Head.Generation + return reflect.DeepEqual(a.Node, b.Node) +} + +func (a RebuiltNode) Merge(b RebuiltNode) (RebuiltNode, error) { + if !a.Compat(b) { + switch { + case a.Node.Head.Generation > b.Node.Head.Generation: + return a, nil + case a.Node.Head.Generation < b.Node.Head.Generation: + return b, nil + default: + return a, fmt.Errorf("mismatch: %v != %v", a, b) + } + } + + // take the broadest region + if a.MinKey.Cmp(b.MinKey) > 0 { // if a.MinKey > b.MinKey { + a.MinKey = b.MinKey // take the min of the two + } + if a.MaxKey.Cmp(b.MaxKey) < 0 { // if a.MaxKey < b.MaxKey { + a.MaxKey = b.MaxKey // take the min of the two + } + + // take the highest generation + a.Node.Head.Generation = slices.Max(a.Node.Head.Generation, b.Node.Head.Generation) + + // take the union + a.InTrees.InsertFrom(b.InTrees) + a.Errs.InsertFrom(b.Errs) + + return a, nil +} + +func reInitBrokenNodes(ctx context.Context, fs _FS, badNodes []badNode) (map[btrfsvol.LogicalAddr]*RebuiltNode, error) { + dlog.Info(ctx, "Re-initializing bad nodes...") + + sb, err := fs.Superblock() + if err != nil { + return nil, err + } + chunkTreeUUID, ok := getChunkTreeUUID(ctx, fs) + if !ok { + return nil, fmt.Errorf("could not look up chunk tree UUID") + } + + sort.Slice(badNodes, func(i, j int) bool { + iGen := badNodes[i].Path.Node(-1).ToNodeGeneration + jGen := badNodes[j].Path.Node(-1).ToNodeGeneration + switch { + case iGen < jGen: + return true + case iGen > jGen: + return false + default: + iAddr := badNodes[i].Path.Node(-1).ToNodeAddr + jAddr := badNodes[j].Path.Node(-1).ToNodeAddr + return iAddr < jAddr + } + }) + + lastPct := -1 + progress := func(done int) { + pct := int(100 * float64(done) / float64(len(badNodes))) + if pct != lastPct || done == len(badNodes) { + dlog.Infof(ctx, "... %v%% (%v/%v)", + pct, done, len(badNodes)) + lastPct = pct + } + } + + rebuiltNodes := make(map[btrfsvol.LogicalAddr]*RebuiltNode) + for i, badNode := range badNodes { + progress(i) + path := badNode.Path + + min, max := spanOfTreePath(fs, path) + node := RebuiltNode{ + Errs: containers.NewSet[string]( + badNode.Err, + ), + MinKey: min, + MaxKey: max, + InTrees: containers.NewSet[btrfsprim.ObjID]( + path.Node(-1).FromTree, + ), + Node: btrfstree.Node{ + Size: sb.NodeSize, + ChecksumType: sb.ChecksumType, + Head: btrfstree.NodeHeader{ + MetadataUUID: sb.EffectiveMetadataUUID(), + Addr: path.Node(-1).ToNodeAddr, + ChunkTreeUUID: chunkTreeUUID, + //Owner: TBD, // see RebuiltNode.InTrees + Generation: path.Node(-1).ToNodeGeneration, + Level: path.Node(-1).ToNodeLevel, + }, + }, + } + if other, ok := rebuiltNodes[path.Node(-1).ToNodeAddr]; ok { + *other, err = other.Merge(node) + if err != nil { + dlog.Errorf(ctx, "... %v", err) + } + } else { + rebuiltNodes[path.Node(-1).ToNodeAddr] = &node + } + } + progress(len(badNodes)) + + dlog.Infof(ctx, "... initialized %d nodes", len(rebuiltNodes)) + return rebuiltNodes, nil +} +*/ diff --git a/lib/btrfsprogs/btrfsinspect/rebuildnodes/bak_s3_reinit_test.go b/lib/btrfsprogs/btrfsinspect/rebuildnodes/bak_s3_reinit_test.go new file mode 100644 index 0000000..865cd7e --- /dev/null +++ b/lib/btrfsprogs/btrfsinspect/rebuildnodes/bak_s3_reinit_test.go @@ -0,0 +1,82 @@ +// Copyright (C) 2022 Luke Shumaker +// +// SPDX-License-Identifier: GPL-2.0-or-later + +package rebuildnodes_test + +/* +import ( + "strings" + "testing" + + "git.lukeshu.com/go/lowmemjson" + "github.com/stretchr/testify/assert" + + "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" + "git.lukeshu.com/btrfs-progs-ng/lib/containers" +) + +func TestEncodeRebuiltNodes(t *testing.T) { + dat := map[btrfsvol.LogicalAddr]*rebuildnodes.RebuiltNode{ + 100007133184: { + Errs: containers.NewSet[string]( + "btrfs.ReadNode: node@0x0000001748e3c000: expected generation\u003c=6596014 but claims to be generation=6596025", + ), + MinKey: btrfsprim.Key{}, + MaxKey: btrfsprim.Key{}, + InTrees: containers.NewSet[btrfsprim.ObjID]( + 257, + ), + Node: btrfstree.Node{}, + }, + } + var buf strings.Builder + assert.NoError(t, lowmemjson.Encode(&lowmemjson.ReEncoder{ + Out: &buf, + + Indent: "\t", + ForceTrailingNewlines: true, + }, dat)) + assert.Equal(t, `{ + "100007133184": { + "Errs": [ + "btrfs.ReadNode: node@0x0000001748e3c000: expected generation\u003c=6596014 but claims to be generation=6596025" + ], + "MinKey": { + "ObjectID": 0, + "ItemType": 0, + "Offset": 0 + }, + "MaxKey": { + "ObjectID": 0, + "ItemType": 0, + "Offset": 0 + }, + "InTrees": [ + 257 + ], + "Size": 0, + "ChecksumType": 0, + "Head": { + "Checksum": "0000000000000000000000000000000000000000000000000000000000000000", + "MetadataUUID": "00000000-0000-0000-0000-000000000000", + "Addr": 0, + "Flags": 0, + "BackrefRev": 0, + "ChunkTreeUUID": "00000000-0000-0000-0000-000000000000", + "Generation": 0, + "Owner": 0, + "NumItems": 0, + "Level": 0 + }, + "BodyInternal": null, + "BodyLeaf": null, + "Padding": null + } +} +`, buf.String()) +} +*/ diff --git a/lib/btrfsprogs/btrfsinspect/rebuildnodes/bak_s4_reattach.go b/lib/btrfsprogs/btrfsinspect/rebuildnodes/bak_s4_reattach.go new file mode 100644 index 0000000..a78d964 --- /dev/null +++ b/lib/btrfsprogs/btrfsinspect/rebuildnodes/bak_s4_reattach.go @@ -0,0 +1,161 @@ +// Copyright (C) 2022 Luke Shumaker +// +// SPDX-License-Identifier: GPL-2.0-or-later + +package rebuildnodes + +/* +import ( + "context" + "sort" + + "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/containers" + "git.lukeshu.com/btrfs-progs-ng/lib/maps" +) + +func (a RebuiltNode) ContainsWholeRegion(min, max btrfsprim.Key) int { + switch { + case min.Cmp(a.MinKey) < 0: + // 'a' is too far right + return -1 + case max.Cmp(a.MaxKey) > 0: + // 'a' is too far left + return 1 + default: + // just right + return 0 + } +} + +func reAttachNodes(ctx context.Context, fs _FS, orphanedNodes containers.Set[btrfsvol.LogicalAddr], rebuiltNodes map[btrfsvol.LogicalAddr]*RebuiltNode) error { + dlog.Info(ctx, "Attaching orphaned nodes to rebuilt nodes...") + + sb, err := fs.Superblock() + if err != nil { + return err + } + + // Index 'rebuiltNodes' for fast lookups. + dlog.Info(ctx, "... indexing rebuilt nodes...") + var byLevel [][]*RebuiltNode + for _, node := range rebuiltNodes { + for int(node.Head.Level) >= len(byLevel) { + byLevel = append(byLevel, []*RebuiltNode(nil)) + } + byLevel[node.Head.Level] = append(byLevel[node.Head.Level], node) + } + for _, slice := range byLevel { + sort.Slice(slice, func(i, j int) bool { + return slice[i].MinKey.Cmp(slice[j].MinKey) < 0 + }) + } + dlog.Info(ctx, "... done indexing") + + // Attach orphanedNodes to the gaps. + dlog.Info(ctx, "... attaching nodes...") + lastPct := -1 + progress := func(done int) { + pct := int(100 * float64(done) / float64(len(orphanedNodes))) + if pct != lastPct || done == len(orphanedNodes) { + dlog.Infof(ctx, "... %v%% (%v/%v)", + pct, done, len(orphanedNodes)) + lastPct = pct + } + } + numAttached := 0 + for i, foundLAddr := range maps.SortedKeys(orphanedNodes) { + progress(i) + foundRef, err := btrfstree.ReadNode[btrfsvol.LogicalAddr](fs, *sb, foundLAddr, btrfstree.NodeExpectations{ + LAddr: containers.Optional[btrfsvol.LogicalAddr]{OK: true, Val: foundLAddr}, + }) + if foundRef == nil { + return err + } + foundMinKey, ok := foundRef.Data.MinItem() + if !ok { + continue + } + foundMaxKey, ok := foundRef.Data.MaxItem() + if !ok { + continue + } + + // `trees` is the set of trees that the node may be + // placed in; '0' is a wildcard that means "any tree". + // We still keep track of the others, in order to try + // to avoid using the wildcard. + trees := make(containers.Set[btrfsprim.ObjID]) + tree := foundRef.Data.Head.Owner + for { + trees.Insert(tree) + var ok bool + tree, ok = fs.ParentTree(tree) + if !ok { + // error; accept anything + trees.Insert(0) + break + } + if tree == 0 { + // end of the line + break + } + } + attached := make(containers.Set[btrfsprim.ObjID]) + for level := int(foundRef.Data.Head.Level) + 1; level < len(byLevel) && len(attached) == 0; level++ { + for _, parent := range byLevel[level] { + if parent.ContainsWholeRegion(foundMinKey, foundMaxKey) != 0 { + continue + } + if parent.Node.Head.Generation < foundRef.Data.Head.Generation { + continue + } + if !trees.HasAny(parent.InTrees) { + continue + } + parent.BodyInternal = append(parent.BodyInternal, btrfstree.KeyPointer{ + Key: foundMinKey, + BlockPtr: foundLAddr, + Generation: foundRef.Data.Head.Generation, + }) + attached.InsertFrom(parent.InTrees) + } + } + if _, wildcard := trees[0]; wildcard && len(attached) == 0 { + for level := int(foundRef.Data.Head.Level) + 1; level < len(byLevel) && len(attached) == 0; level++ { + for _, parent := range byLevel[level] { + if parent.ContainsWholeRegion(foundMinKey, foundMaxKey) != 0 { + continue + } + if parent.Node.Head.Generation < foundRef.Data.Head.Generation { + continue + } + parent.BodyInternal = append(parent.BodyInternal, btrfstree.KeyPointer{ + Key: foundMinKey, + BlockPtr: foundLAddr, + Generation: foundRef.Data.Head.Generation, + }) + attached.InsertFrom(parent.InTrees) + } + } + } + + if len(attached) > 0 { + numAttached++ + } else { + dlog.Errorf(ctx, "could not find a broken node to attach node to reattach node@%v to", + foundRef.Addr) + } + } + progress(len(orphanedNodes)) + dlog.Info(ctx, "... ... done attaching") + + dlog.Infof(ctx, "... re-attached %d nodes (%v%% success rate)", + numAttached, int(100*float64(numAttached)/float64(len(orphanedNodes)))) + return nil +} +*/ diff --git a/lib/btrfsprogs/btrfsinspect/rebuildnodes/rebuildnodes.go b/lib/btrfsprogs/btrfsinspect/rebuildnodes/rebuildnodes.go deleted file mode 100644 index 34b470e..0000000 --- a/lib/btrfsprogs/btrfsinspect/rebuildnodes/rebuildnodes.go +++ /dev/null @@ -1,117 +0,0 @@ -// Copyright (C) 2022 Luke Shumaker -// -// SPDX-License-Identifier: GPL-2.0-or-later - -package rebuildnodes - -import ( - "context" - - "git.lukeshu.com/btrfs-progs-ng/lib/btrfs" - "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" - "git.lukeshu.com/btrfs-progs-ng/lib/btrfsprogs/btrfsutil" - "git.lukeshu.com/btrfs-progs-ng/lib/containers" - "git.lukeshu.com/btrfs-progs-ng/lib/diskio" -) - -func RebuildNodes(ctx context.Context, fs *btrfs.FS, nodeScanResults btrfsinspect.ScanDevicesResult) (map[btrfsvol.LogicalAddr]*RebuiltNode, error) { - uuidMap, err := buildUUIDMap(ctx, fs, nodeScanResults) - if err != nil { - return nil, err - } - - nfs := &RebuiltTrees{ - inner: fs, - uuidMap: uuidMap, - } - - orphanedNodes, badNodes, treeAncestors, err := classifyNodes(ctx, nfs, nodeScanResults) - if err != nil { - return nil, err - } - - uuidMap.considerAncestors(ctx, treeAncestors) - - rebuiltNodes, err := reInitBrokenNodes(ctx, nfs, badNodes) - if err != nil { - return nil, err - } - - if err := reAttachNodes(ctx, nfs, orphanedNodes, rebuiltNodes); err != nil { - return nil, err - } - - return rebuiltNodes, nil -} - -func spanOfTreePath(fs _FS, path btrfstree.TreePath) (btrfsprim.Key, btrfsprim.Key) { - // tree root error - if len(path) == 0 { - return btrfsprim.Key{}, maxKey - } - - // item error - if path.Node(-1).ToNodeAddr == 0 { - // If we got an item error, then the node is readable - node, _ := fs.ReadNode(path.Parent()) - key := node.Data.BodyLeaf[path.Node(-1).FromItemIdx].Key - return key, key - } - - // node error - // - // assume that path.Node(-1).ToNodeAddr is not readable, but that path.Node(-2).ToNodeAddr is. - if len(path) == 1 { - return btrfsprim.Key{}, maxKey - } - parentNode, _ := fs.ReadNode(path.Parent()) - low := parentNode.Data.BodyInternal[path.Node(-1).FromItemIdx].Key - var high btrfsprim.Key - if path.Node(-1).FromItemIdx+1 < len(parentNode.Data.BodyInternal) { - high = keyMm(parentNode.Data.BodyInternal[path.Node(-1).FromItemIdx+1].Key) - } else { - parentPath := path.Parent().DeepCopy() - _, high = spanOfTreePath(fs, parentPath) - } - return low, high -} - -func walkFromNode(ctx context.Context, fs _FS, nodeAddr btrfsvol.LogicalAddr, errHandle func(*btrfstree.TreeError), cbs btrfstree.TreeWalkHandler) { - sb, _ := fs.Superblock() - nodeRef, _ := btrfstree.ReadNode[btrfsvol.LogicalAddr](fs, *sb, nodeAddr, btrfstree.NodeExpectations{ - LAddr: containers.Optional[btrfsvol.LogicalAddr]{OK: true, Val: nodeAddr}, - }) - if nodeRef == nil { - return - } - treeInfo := btrfstree.TreeRoot{ - TreeID: nodeRef.Data.Head.Owner, - RootNode: nodeAddr, - Level: nodeRef.Data.Head.Level, - Generation: nodeRef.Data.Head.Generation, - } - btrfstree.TreeOperatorImpl{NodeSource: fs}.RawTreeWalk(ctx, treeInfo, errHandle, cbs) -} - -func getChunkTreeUUID(ctx context.Context, fs _FS) (btrfsprim.UUID, bool) { - ctx, cancel := context.WithCancel(ctx) - var ret btrfsprim.UUID - var retOK bool - btrfsutil.WalkAllTrees(ctx, fs, btrfsutil.WalkAllTreesHandler{ - TreeWalkHandler: btrfstree.TreeWalkHandler{ - Node: func(path btrfstree.TreePath, node *diskio.Ref[btrfsvol.LogicalAddr, btrfstree.Node]) error { - ret = node.Data.Head.ChunkTreeUUID - retOK = true - cancel() - return nil - }, - }, - Err: func(err *btrfsutil.WalkError) { - // do nothing - }, - }) - return ret, retOK -} diff --git a/lib/btrfsprogs/btrfsinspect/rebuildnodes/rebuilttrees.go b/lib/btrfsprogs/btrfsinspect/rebuildnodes/rebuilttrees.go deleted file mode 100644 index da956de..0000000 --- a/lib/btrfsprogs/btrfsinspect/rebuildnodes/rebuilttrees.go +++ /dev/null @@ -1,87 +0,0 @@ -// Copyright (C) 2022 Luke Shumaker -// -// SPDX-License-Identifier: GPL-2.0-or-later - -package rebuildnodes - -import ( - "context" - "fmt" - - "git.lukeshu.com/btrfs-progs-ng/lib/btrfs" - "git.lukeshu.com/btrfs-progs-ng/lib/btrfs/btrfsprim" - "git.lukeshu.com/btrfs-progs-ng/lib/btrfs/btrfstree" - "git.lukeshu.com/btrfs-progs-ng/lib/btrfs/btrfsvol" - "git.lukeshu.com/btrfs-progs-ng/lib/diskio" -) - -type RebuiltTrees struct { - inner *btrfs.FS - uuidMap uuidMap - nodes map[btrfsvol.LogicalAddr]*RebuiltNode -} - -type _FS interface { - diskio.File[btrfsvol.LogicalAddr] - btrfstree.NodeFile - btrfstree.NodeSource - btrfstree.TreeOperator -} - -// diskio.File - -func (fs *RebuiltTrees) Name() string { return fs.inner.Name() } -func (fs *RebuiltTrees) Size() btrfsvol.LogicalAddr { return fs.inner.Size() } -func (fs *RebuiltTrees) Close() error { return fs.inner.Close() } -func (fs *RebuiltTrees) ReadAt(p []byte, off btrfsvol.LogicalAddr) (int, error) { - sb, err := fs.Superblock() - if err != nil { - return 0, err - } - if rebuilt, ok := fs.nodes[off]; ok && len(p) == int(sb.NodeSize) { - rebuilt.Node.Head.Checksum, err = rebuilt.Node.CalculateChecksum() - if err != nil { - panic(fmt.Errorf("should not happen: %w", err)) - } - bs, err := rebuilt.Node.MarshalBinary() - if err != nil { - panic(fmt.Errorf("should not happen: %w", err)) - } - if len(p) != len(bs) { - panic(fmt.Errorf("should not happen: sb.NodeSize=%v but node marshaled to %v", sb.NodeSize, len(bs))) - } - return copy(p, bs), nil - } - return fs.inner.ReadAt(p, off) -} -func (fs *RebuiltTrees) WriteAt(p []byte, off btrfsvol.LogicalAddr) (int, error) { - return fs.inner.WriteAt(p, off) -} - -// btrfstree.NodeFile - -func (fs *RebuiltTrees) ParentTree(tree btrfsprim.ObjID) (btrfsprim.ObjID, bool) { - return fs.uuidMap.ParentTree(tree) -} - -// btrfstree.NodeSource - -func (fs *RebuiltTrees) Superblock() (*btrfstree.Superblock, error) { return fs.inner.Superblock() } -func (fs *RebuiltTrees) ReadNode(path btrfstree.TreePath) (*diskio.Ref[btrfsvol.LogicalAddr, btrfstree.Node], error) { - return btrfstree.FSReadNode(fs, path) -} - -// btrfstree.TreeOperator - -func (fs *RebuiltTrees) TreeWalk(ctx context.Context, treeID btrfsprim.ObjID, errHandle func(*btrfstree.TreeError), cbs btrfstree.TreeWalkHandler) { - btrfstree.TreeOperatorImpl{NodeSource: fs}.TreeWalk(ctx, treeID, errHandle, cbs) -} -func (fs *RebuiltTrees) TreeLookup(treeID btrfsprim.ObjID, key btrfsprim.Key) (btrfstree.Item, error) { - return btrfstree.TreeOperatorImpl{NodeSource: fs}.TreeLookup(treeID, key) -} -func (fs *RebuiltTrees) TreeSearch(treeID btrfsprim.ObjID, fn func(key btrfsprim.Key, size uint32) int) (btrfstree.Item, error) { - return btrfstree.TreeOperatorImpl{NodeSource: fs}.TreeSearch(treeID, fn) -} -func (fs *RebuiltTrees) TreeSearchAll(treeID btrfsprim.ObjID, fn func(key btrfsprim.Key, size uint32) int) ([]btrfstree.Item, error) { - return btrfstree.TreeOperatorImpl{NodeSource: fs}.TreeSearchAll(treeID, fn) -} diff --git a/lib/btrfsprogs/btrfsinspect/rebuildnodes/s1_uuidmap.go b/lib/btrfsprogs/btrfsinspect/rebuildnodes/s1_uuidmap.go deleted file mode 100644 index 8a5e745..0000000 --- a/lib/btrfsprogs/btrfsinspect/rebuildnodes/s1_uuidmap.go +++ /dev/null @@ -1,20 +0,0 @@ -// Copyright (C) 2022 Luke Shumaker -// -// SPDX-License-Identifier: GPL-2.0-or-later - -package rebuildnodes - -import ( - "context" - - "git.lukeshu.com/btrfs-progs-ng/lib/btrfs" - "git.lukeshu.com/btrfs-progs-ng/lib/btrfsprogs/btrfsinspect" -) - -func buildUUIDMap(ctx context.Context, fs *btrfs.FS, scanResults btrfsinspect.ScanDevicesResult) (uuidMap, error) { - ret, err := ScanDevices(ctx, fs, scanResults) - if err != nil { - return uuidMap{}, err - } - return ret.uuidMap, nil -} diff --git a/lib/btrfsprogs/btrfsinspect/rebuildnodes/s2_classify.go b/lib/btrfsprogs/btrfsinspect/rebuildnodes/s2_classify.go deleted file mode 100644 index 6adddc3..0000000 --- a/lib/btrfsprogs/btrfsinspect/rebuildnodes/s2_classify.go +++ /dev/null @@ -1,141 +0,0 @@ -// Copyright (C) 2022 Luke Shumaker -// -// SPDX-License-Identifier: GPL-2.0-or-later - -package rebuildnodes - -import ( - "context" - "errors" - iofs "io/fs" - - "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" - "git.lukeshu.com/btrfs-progs-ng/lib/btrfsprogs/btrfsutil" - "git.lukeshu.com/btrfs-progs-ng/lib/containers" - "git.lukeshu.com/btrfs-progs-ng/lib/diskio" - "git.lukeshu.com/btrfs-progs-ng/lib/maps" -) - -type badNode struct { - Err string - Path btrfstree.TreePath -} - -// classifyNodes returns -// -// 1. the set of nodes don't have another node claiming it as a child, and -// 2. the list of bad nodes (in no particular order) -// 3. tree ancestors thing -func classifyNodes(ctx context.Context, fs _FS, scanResults btrfsinspect.ScanDevicesResult) ( - orphanedNodes containers.Set[btrfsvol.LogicalAddr], - badNodes []badNode, - treeAncestors map[btrfsprim.ObjID]containers.Set[btrfsprim.ObjID], - err error, -) { - dlog.Info(ctx, "Walking trees to identify orphan and broken nodes...") - - lastPct := -1 - total := countNodes(scanResults) - visitedNodes := make(containers.Set[btrfsvol.LogicalAddr]) - progress := func() { - done := len(visitedNodes) - pct := int(100 * float64(done) / float64(total)) - if pct != lastPct || done == total { - dlog.Infof(ctx, "... %v%% (%v/%v)", - pct, done, total) - lastPct = pct - } - } - - treeAncestors = make(map[btrfsprim.ObjID]containers.Set[btrfsprim.ObjID]) - - var potentialRoot btrfsvol.LogicalAddr // zero for non-lost nodes, non-zero for lost nodes - nodeHandler := func(path btrfstree.TreePath, nodeRef *diskio.Ref[btrfsvol.LogicalAddr, btrfstree.Node], err error) error { - if err != nil && (errors.Is(err, btrfstree.ErrNotANode) || errors.As(err, new(*btrfstree.IOError))) { - badNodes = append(badNodes, badNode{ - Err: err.Error(), - Path: path.DeepCopy(), - }) - return err - } - addr := path.Node(-1).ToNodeAddr - visitedNodes.Insert(addr) - if potentialRoot != 0 { - // lost node - if addr != potentialRoot { - delete(orphanedNodes, addr) - } - } - if err == nil && nodeRef.Data.Head.Owner != path.Node(-1).FromTree { - if treeAncestors[path.Node(-1).FromTree] == nil { - treeAncestors[path.Node(-1).FromTree] = make(containers.Set[btrfsprim.ObjID]) - } - treeAncestors[path.Node(-1).FromTree].Insert(nodeRef.Data.Head.Owner) - } - progress() - return nil - } - - walkHandler := btrfstree.TreeWalkHandler{ - PreNode: func(path btrfstree.TreePath) error { - addr := path.Node(-1).ToNodeAddr - if visitedNodes.Has(addr) { - // Can happen because of COW subvolumes; - // this is really a DAG not a tree. - return iofs.SkipDir - } - return nil - }, - Node: func(path btrfstree.TreePath, nodeRef *diskio.Ref[btrfsvol.LogicalAddr, btrfstree.Node]) error { - return nodeHandler(path, nodeRef, nil) - }, - BadNode: func(path btrfstree.TreePath, nodeRef *diskio.Ref[btrfsvol.LogicalAddr, btrfstree.Node], err error) error { - return nodeHandler(path, nodeRef, err) - }, - } - - progress() - btrfsutil.WalkAllTrees(ctx, fs, btrfsutil.WalkAllTreesHandler{ - TreeWalkHandler: walkHandler, - Err: func(err *btrfsutil.WalkError) { - // do nothing - }, - }) - - // Start with 'orphanedRoots' as a complete set of all orphaned nodes, and then delete - // non-root entries from it. - orphanedNodes = make(containers.Set[btrfsvol.LogicalAddr]) - for _, devResults := range scanResults { - for laddr := range devResults.FoundNodes { - if !visitedNodes.Has(laddr) { - orphanedNodes.Insert(laddr) - } - } - } - if len(visitedNodes)+len(orphanedNodes) != total { - panic("should not happen") - } - dlog.Infof(ctx, - "... (finished processing %v attached nodes, proceeding to process %v lost nodes, for a total of %v)", - len(visitedNodes), len(orphanedNodes), len(visitedNodes)+len(orphanedNodes)) - for _, potentialRoot = range maps.SortedKeys(orphanedNodes) { - walkFromNode(ctx, fs, potentialRoot, - func(err *btrfstree.TreeError) { - // do nothing - }, - walkHandler, - ) - } - - if len(visitedNodes) != total { - panic("should not happen") - } - - dlog.Infof(ctx, "... identified %d orphaned nodes and %d bad nodes", len(orphanedNodes), len(badNodes)) - return orphanedNodes, badNodes, treeAncestors, nil -} diff --git a/lib/btrfsprogs/btrfsinspect/rebuildnodes/s3_reinit.go b/lib/btrfsprogs/btrfsinspect/rebuildnodes/s3_reinit.go deleted file mode 100644 index 7b43d28..0000000 --- a/lib/btrfsprogs/btrfsinspect/rebuildnodes/s3_reinit.go +++ /dev/null @@ -1,142 +0,0 @@ -// Copyright (C) 2022 Luke Shumaker -// -// SPDX-License-Identifier: GPL-2.0-or-later - -package rebuildnodes - -import ( - "context" - "fmt" - "reflect" - "sort" - - "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/containers" - "git.lukeshu.com/btrfs-progs-ng/lib/slices" -) - -type RebuiltNode struct { - Errs containers.Set[string] - MinKey, MaxKey btrfsprim.Key - InTrees containers.Set[btrfsprim.ObjID] - btrfstree.Node -} - -func (a RebuiltNode) Compat(b RebuiltNode) bool { - a.Node.Head.Generation = b.Node.Head.Generation - return reflect.DeepEqual(a.Node, b.Node) -} - -func (a RebuiltNode) Merge(b RebuiltNode) (RebuiltNode, error) { - if !a.Compat(b) { - switch { - case a.Node.Head.Generation > b.Node.Head.Generation: - return a, nil - case a.Node.Head.Generation < b.Node.Head.Generation: - return b, nil - default: - return a, fmt.Errorf("mismatch: %v != %v", a, b) - } - } - - // take the broadest region - if a.MinKey.Cmp(b.MinKey) > 0 { // if a.MinKey > b.MinKey { - a.MinKey = b.MinKey // take the min of the two - } - if a.MaxKey.Cmp(b.MaxKey) < 0 { // if a.MaxKey < b.MaxKey { - a.MaxKey = b.MaxKey // take the min of the two - } - - // take the highest generation - a.Node.Head.Generation = slices.Max(a.Node.Head.Generation, b.Node.Head.Generation) - - // take the union - a.InTrees.InsertFrom(b.InTrees) - a.Errs.InsertFrom(b.Errs) - - return a, nil -} - -func reInitBrokenNodes(ctx context.Context, fs _FS, badNodes []badNode) (map[btrfsvol.LogicalAddr]*RebuiltNode, error) { - dlog.Info(ctx, "Re-initializing bad nodes...") - - sb, err := fs.Superblock() - if err != nil { - return nil, err - } - chunkTreeUUID, ok := getChunkTreeUUID(ctx, fs) - if !ok { - return nil, fmt.Errorf("could not look up chunk tree UUID") - } - - sort.Slice(badNodes, func(i, j int) bool { - iGen := badNodes[i].Path.Node(-1).ToNodeGeneration - jGen := badNodes[j].Path.Node(-1).ToNodeGeneration - switch { - case iGen < jGen: - return true - case iGen > jGen: - return false - default: - iAddr := badNodes[i].Path.Node(-1).ToNodeAddr - jAddr := badNodes[j].Path.Node(-1).ToNodeAddr - return iAddr < jAddr - } - }) - - lastPct := -1 - progress := func(done int) { - pct := int(100 * float64(done) / float64(len(badNodes))) - if pct != lastPct || done == len(badNodes) { - dlog.Infof(ctx, "... %v%% (%v/%v)", - pct, done, len(badNodes)) - lastPct = pct - } - } - - rebuiltNodes := make(map[btrfsvol.LogicalAddr]*RebuiltNode) - for i, badNode := range badNodes { - progress(i) - path := badNode.Path - - min, max := spanOfTreePath(fs, path) - node := RebuiltNode{ - Errs: containers.NewSet[string]( - badNode.Err, - ), - MinKey: min, - MaxKey: max, - InTrees: containers.NewSet[btrfsprim.ObjID]( - path.Node(-1).FromTree, - ), - Node: btrfstree.Node{ - Size: sb.NodeSize, - ChecksumType: sb.ChecksumType, - Head: btrfstree.NodeHeader{ - MetadataUUID: sb.EffectiveMetadataUUID(), - Addr: path.Node(-1).ToNodeAddr, - ChunkTreeUUID: chunkTreeUUID, - //Owner: TBD, // see RebuiltNode.InTrees - Generation: path.Node(-1).ToNodeGeneration, - Level: path.Node(-1).ToNodeLevel, - }, - }, - } - if other, ok := rebuiltNodes[path.Node(-1).ToNodeAddr]; ok { - *other, err = other.Merge(node) - if err != nil { - dlog.Errorf(ctx, "... %v", err) - } - } else { - rebuiltNodes[path.Node(-1).ToNodeAddr] = &node - } - } - progress(len(badNodes)) - - dlog.Infof(ctx, "... initialized %d nodes", len(rebuiltNodes)) - return rebuiltNodes, nil -} diff --git a/lib/btrfsprogs/btrfsinspect/rebuildnodes/s3_reinit_test.go b/lib/btrfsprogs/btrfsinspect/rebuildnodes/s3_reinit_test.go deleted file mode 100644 index badfdfc..0000000 --- a/lib/btrfsprogs/btrfsinspect/rebuildnodes/s3_reinit_test.go +++ /dev/null @@ -1,80 +0,0 @@ -// Copyright (C) 2022 Luke Shumaker -// -// SPDX-License-Identifier: GPL-2.0-or-later - -package rebuildnodes_test - -import ( - "strings" - "testing" - - "git.lukeshu.com/go/lowmemjson" - "github.com/stretchr/testify/assert" - - "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" - "git.lukeshu.com/btrfs-progs-ng/lib/containers" -) - -func TestEncodeRebuiltNodes(t *testing.T) { - dat := map[btrfsvol.LogicalAddr]*rebuildnodes.RebuiltNode{ - 100007133184: { - Errs: containers.NewSet[string]( - "btrfs.ReadNode: node@0x0000001748e3c000: expected generation\u003c=6596014 but claims to be generation=6596025", - ), - MinKey: btrfsprim.Key{}, - MaxKey: btrfsprim.Key{}, - InTrees: containers.NewSet[btrfsprim.ObjID]( - 257, - ), - Node: btrfstree.Node{}, - }, - } - var buf strings.Builder - assert.NoError(t, lowmemjson.Encode(&lowmemjson.ReEncoder{ - Out: &buf, - - Indent: "\t", - ForceTrailingNewlines: true, - }, dat)) - assert.Equal(t, `{ - "100007133184": { - "Errs": [ - "btrfs.ReadNode: node@0x0000001748e3c000: expected generation\u003c=6596014 but claims to be generation=6596025" - ], - "MinKey": { - "ObjectID": 0, - "ItemType": 0, - "Offset": 0 - }, - "MaxKey": { - "ObjectID": 0, - "ItemType": 0, - "Offset": 0 - }, - "InTrees": [ - 257 - ], - "Size": 0, - "ChecksumType": 0, - "Head": { - "Checksum": "0000000000000000000000000000000000000000000000000000000000000000", - "MetadataUUID": "00000000-0000-0000-0000-000000000000", - "Addr": 0, - "Flags": 0, - "BackrefRev": 0, - "ChunkTreeUUID": "00000000-0000-0000-0000-000000000000", - "Generation": 0, - "Owner": 0, - "NumItems": 0, - "Level": 0 - }, - "BodyInternal": null, - "BodyLeaf": null, - "Padding": null - } -} -`, buf.String()) -} diff --git a/lib/btrfsprogs/btrfsinspect/rebuildnodes/s4_reattach.go b/lib/btrfsprogs/btrfsinspect/rebuildnodes/s4_reattach.go deleted file mode 100644 index ef7d284..0000000 --- a/lib/btrfsprogs/btrfsinspect/rebuildnodes/s4_reattach.go +++ /dev/null @@ -1,159 +0,0 @@ -// Copyright (C) 2022 Luke Shumaker -// -// SPDX-License-Identifier: GPL-2.0-or-later - -package rebuildnodes - -import ( - "context" - "sort" - - "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/containers" - "git.lukeshu.com/btrfs-progs-ng/lib/maps" -) - -func (a RebuiltNode) ContainsWholeRegion(min, max btrfsprim.Key) int { - switch { - case min.Cmp(a.MinKey) < 0: - // 'a' is too far right - return -1 - case max.Cmp(a.MaxKey) > 0: - // 'a' is too far left - return 1 - default: - // just right - return 0 - } -} - -func reAttachNodes(ctx context.Context, fs _FS, orphanedNodes containers.Set[btrfsvol.LogicalAddr], rebuiltNodes map[btrfsvol.LogicalAddr]*RebuiltNode) error { - dlog.Info(ctx, "Attaching orphaned nodes to rebuilt nodes...") - - sb, err := fs.Superblock() - if err != nil { - return err - } - - // Index 'rebuiltNodes' for fast lookups. - dlog.Info(ctx, "... indexing rebuilt nodes...") - var byLevel [][]*RebuiltNode - for _, node := range rebuiltNodes { - for int(node.Head.Level) >= len(byLevel) { - byLevel = append(byLevel, []*RebuiltNode(nil)) - } - byLevel[node.Head.Level] = append(byLevel[node.Head.Level], node) - } - for _, slice := range byLevel { - sort.Slice(slice, func(i, j int) bool { - return slice[i].MinKey.Cmp(slice[j].MinKey) < 0 - }) - } - dlog.Info(ctx, "... done indexing") - - // Attach orphanedNodes to the gaps. - dlog.Info(ctx, "... attaching nodes...") - lastPct := -1 - progress := func(done int) { - pct := int(100 * float64(done) / float64(len(orphanedNodes))) - if pct != lastPct || done == len(orphanedNodes) { - dlog.Infof(ctx, "... %v%% (%v/%v)", - pct, done, len(orphanedNodes)) - lastPct = pct - } - } - numAttached := 0 - for i, foundLAddr := range maps.SortedKeys(orphanedNodes) { - progress(i) - foundRef, err := btrfstree.ReadNode[btrfsvol.LogicalAddr](fs, *sb, foundLAddr, btrfstree.NodeExpectations{ - LAddr: containers.Optional[btrfsvol.LogicalAddr]{OK: true, Val: foundLAddr}, - }) - if foundRef == nil { - return err - } - foundMinKey, ok := foundRef.Data.MinItem() - if !ok { - continue - } - foundMaxKey, ok := foundRef.Data.MaxItem() - if !ok { - continue - } - - // `trees` is the set of trees that the node may be - // placed in; '0' is a wildcard that means "any tree". - // We still keep track of the others, in order to try - // to avoid using the wildcard. - trees := make(containers.Set[btrfsprim.ObjID]) - tree := foundRef.Data.Head.Owner - for { - trees.Insert(tree) - var ok bool - tree, ok = fs.ParentTree(tree) - if !ok { - // error; accept anything - trees.Insert(0) - break - } - if tree == 0 { - // end of the line - break - } - } - attached := make(containers.Set[btrfsprim.ObjID]) - for level := int(foundRef.Data.Head.Level) + 1; level < len(byLevel) && len(attached) == 0; level++ { - for _, parent := range byLevel[level] { - if parent.ContainsWholeRegion(foundMinKey, foundMaxKey) != 0 { - continue - } - if parent.Node.Head.Generation < foundRef.Data.Head.Generation { - continue - } - if !trees.HasAny(parent.InTrees) { - continue - } - parent.BodyInternal = append(parent.BodyInternal, btrfstree.KeyPointer{ - Key: foundMinKey, - BlockPtr: foundLAddr, - Generation: foundRef.Data.Head.Generation, - }) - attached.InsertFrom(parent.InTrees) - } - } - if _, wildcard := trees[0]; wildcard && len(attached) == 0 { - for level := int(foundRef.Data.Head.Level) + 1; level < len(byLevel) && len(attached) == 0; level++ { - for _, parent := range byLevel[level] { - if parent.ContainsWholeRegion(foundMinKey, foundMaxKey) != 0 { - continue - } - if parent.Node.Head.Generation < foundRef.Data.Head.Generation { - continue - } - parent.BodyInternal = append(parent.BodyInternal, btrfstree.KeyPointer{ - Key: foundMinKey, - BlockPtr: foundLAddr, - Generation: foundRef.Data.Head.Generation, - }) - attached.InsertFrom(parent.InTrees) - } - } - } - - if len(attached) > 0 { - numAttached++ - } else { - dlog.Errorf(ctx, "could not find a broken node to attach node to reattach node@%v to", - foundRef.Addr) - } - } - progress(len(orphanedNodes)) - dlog.Info(ctx, "... ... done attaching") - - dlog.Infof(ctx, "... re-attached %d nodes (%v%% success rate)", - numAttached, int(100*float64(numAttached)/float64(len(orphanedNodes)))) - return nil -} diff --git a/lib/btrfsprogs/btrfsinspect/rebuildnodes/scan.go b/lib/btrfsprogs/btrfsinspect/rebuildnodes/scan.go index cd3f59e..5070e7e 100644 --- a/lib/btrfsprogs/btrfsinspect/rebuildnodes/scan.go +++ b/lib/btrfsprogs/btrfsinspect/rebuildnodes/scan.go @@ -6,6 +6,7 @@ package rebuildnodes import ( "context" + "fmt" "github.com/datawire/dlib/dlog" @@ -20,32 +21,55 @@ import ( ) type nodeData struct { - Level uint8 // 0+1=1 - Generation btrfsprim.Generation // 1+8=9 - Owner btrfsprim.ObjID // 9+8=17 - MinItem btrfsprim.Key // 17+17=34 - MaxItem btrfsprim.Key // 34+17=51 + Level uint8 + Generation btrfsprim.Generation + Owner btrfsprim.ObjID + NumItems uint32 + MinItem btrfsprim.Key + MaxItem btrfsprim.Key } type kpData struct { - From, To btrfsvol.LogicalAddr // 0+(2*8)=16 - Key btrfsprim.Key // 16+17=33 - Generation btrfsprim.Generation // 33+8=41 + FromTree btrfsprim.ObjID + FromNode btrfsvol.LogicalAddr + FromItem int + + ToNode btrfsvol.LogicalAddr + ToLevel uint8 + ToKey btrfsprim.Key + ToGeneration btrfsprim.Generation } type nodeGraph struct { Nodes map[btrfsvol.LogicalAddr]nodeData + BadNodes map[btrfsvol.LogicalAddr]error EdgesFrom map[btrfsvol.LogicalAddr][]*kpData EdgesTo map[btrfsvol.LogicalAddr][]*kpData } +func (g nodeGraph) insertEdge(kp kpData) { + ptr := &kp + g.EdgesFrom[kp.FromNode] = append(g.EdgesFrom[kp.FromNode], ptr) + g.EdgesTo[kp.ToNode] = append(g.EdgesTo[kp.ToNode], ptr) +} + +func (g nodeGraph) insertTreeRoot(sb btrfstree.Superblock, treeID btrfsprim.ObjID) { + treeInfo, _ := btrfstree.LookupTreeRoot(nil, sb, treeID) + g.insertEdge(kpData{ + FromTree: treeID, + ToNode: treeInfo.RootNode, + ToLevel: treeInfo.Level, + ToGeneration: treeInfo.Generation, + }) +} + type scanResult struct { uuidMap nodeGraph } func ScanDevices(ctx context.Context, fs *btrfs.FS, scanResults btrfsinspect.ScanDevicesResult) (*scanResult, error) { - dlog.Infof(ctx, "Building table of ObjID←→UUID...") + dlog.Infof(ctx, "Reading node data from FS...") sb, err := fs.Superblock() if err != nil { @@ -74,6 +98,7 @@ func ScanDevices(ctx context.Context, fs *btrfs.FS, scanResults btrfsinspect.Sca }, nodeGraph: nodeGraph{ Nodes: make(map[btrfsvol.LogicalAddr]nodeData), + BadNodes: make(map[btrfsvol.LogicalAddr]error), EdgesFrom: make(map[btrfsvol.LogicalAddr][]*kpData), EdgesTo: make(map[btrfsvol.LogicalAddr][]*kpData), }, @@ -81,10 +106,19 @@ func ScanDevices(ctx context.Context, fs *btrfs.FS, scanResults btrfsinspect.Sca // These 4 trees are mentioned directly in the superblock, so // they are always seen. + // + // 1 ret.SeenTrees.Insert(btrfsprim.ROOT_TREE_OBJECTID) + ret.insertTreeRoot(*sb, btrfsprim.ROOT_TREE_OBJECTID) + // 2 ret.SeenTrees.Insert(btrfsprim.CHUNK_TREE_OBJECTID) + ret.insertTreeRoot(*sb, btrfsprim.CHUNK_TREE_OBJECTID) + // 3 ret.SeenTrees.Insert(btrfsprim.TREE_LOG_OBJECTID) + ret.insertTreeRoot(*sb, btrfsprim.TREE_LOG_OBJECTID) + // 4 ret.SeenTrees.Insert(btrfsprim.BLOCK_GROUP_TREE_OBJECTID) + ret.insertTreeRoot(*sb, btrfsprim.BLOCK_GROUP_TREE_OBJECTID) progress() for _, devResults := range scanResults { @@ -112,6 +146,13 @@ func ScanDevices(ctx context.Context, fs *btrfs.FS, scanResults btrfsinspect.Sca return nil, err } ret.SeenTrees.Insert(item.Key.ObjectID) + // graph building + ret.insertEdge(kpData{ + FromTree: item.Key.ObjectID, + ToNode: itemBody.ByteNr, + ToLevel: itemBody.Level, + ToGeneration: itemBody.Generation, + }) case btrfsitem.UUIDMap: uuid := btrfsitem.KeyToUUID(item.Key) if err := maybeSet("ObjID2UUID", ret.ObjID2UUID, itemBody.ObjID, uuid); err != nil { @@ -132,15 +173,16 @@ func ScanDevices(ctx context.Context, fs *btrfs.FS, scanResults btrfsinspect.Sca MinItem: func() btrfsprim.Key { k, _ := nodeRef.Data.MinItem(); return k }(), MaxItem: func() btrfsprim.Key { k, _ := nodeRef.Data.MaxItem(); return k }(), } - for _, kp := range nodeRef.Data.BodyInternal { - dat := &kpData{ - From: laddr, - To: kp.BlockPtr, - Key: kp.Key, - Generation: kp.Generation, - } - ret.EdgesFrom[laddr] = append(ret.EdgesFrom[laddr], dat) - ret.EdgesTo[laddr] = append(ret.EdgesTo[laddr], dat) + for i, kp := range nodeRef.Data.BodyInternal { + ret.insertEdge(kpData{ + FromTree: nodeRef.Data.Head.Owner, + FromNode: laddr, + FromItem: i, + ToNode: kp.BlockPtr, + ToLevel: nodeRef.Data.Head.Level - 1, + ToKey: kp.Key, + ToGeneration: kp.Generation, + }) } done++ @@ -157,6 +199,26 @@ func ScanDevices(ctx context.Context, fs *btrfs.FS, scanResults btrfsinspect.Sca dlog.Errorf(ctx, "... could not find root items for %d trees: %v", len(missing), maps.SortedKeys(missing)) } - dlog.Info(ctx, "... done building table") + dlog.Info(ctx, "... done reading node data") + + dlog.Infof(ctx, "Checking keypointers for dead-ends...") + total = len(ret.EdgesTo) + done = 0 + progress() + for laddr := range ret.EdgesTo { + if _, ok := ret.Nodes[laddr]; !ok { + _, err := btrfstree.ReadNode[btrfsvol.LogicalAddr](fs, *sb, laddr, btrfstree.NodeExpectations{ + LAddr: containers.Optional[btrfsvol.LogicalAddr]{OK: true, Val: laddr}, + }) + if err == nil { + return nil, fmt.Errorf("node@%v exists but was not in node scan results", laddr) + } + ret.BadNodes[laddr] = err + } + done++ + progress() + } + dlog.Info(ctx, "... done checking keypointers") + return ret, nil } diff --git a/lib/btrfsprogs/btrfsinspect/rebuildnodes/treeancestors.go b/lib/btrfsprogs/btrfsinspect/rebuildnodes/treeancestors.go new file mode 100644 index 0000000..2e1d856 --- /dev/null +++ b/lib/btrfsprogs/btrfsinspect/rebuildnodes/treeancestors.go @@ -0,0 +1,25 @@ +// Copyright (C) 2022 Luke Shumaker +// +// SPDX-License-Identifier: GPL-2.0-or-later + +package rebuildnodes + +import ( + "git.lukeshu.com/btrfs-progs-ng/lib/btrfs/btrfsprim" + "git.lukeshu.com/btrfs-progs-ng/lib/containers" +) + +func getTreeAncestors(scanData scanResult) map[btrfsprim.ObjID]containers.Set[btrfsprim.ObjID] { + treeAncestors := make(map[btrfsprim.ObjID]containers.Set[btrfsprim.ObjID]) + + for laddr, node := range scanData.Nodes { + if _, ok := treeAncestors[node.Owner]; !ok { + treeAncestors[node.Owner] = make(containers.Set[btrfsprim.ObjID]) + } + for _, edge := range scanData.EdgesTo[laddr] { + treeAncestors[node.Owner].Insert(edge.FromTree) + } + } + + return treeAncestors +} diff --git a/lib/btrfsprogs/btrfsinspect/rebuildnodes/util.go b/lib/btrfsprogs/btrfsinspect/rebuildnodes/util.go index f9e4e95..7e0eab1 100644 --- a/lib/btrfsprogs/btrfsinspect/rebuildnodes/util.go +++ b/lib/btrfsprogs/btrfsinspect/rebuildnodes/util.go @@ -6,9 +6,7 @@ package rebuildnodes import ( "fmt" - "math" - "git.lukeshu.com/btrfs-progs-ng/lib/btrfs/btrfsprim" "git.lukeshu.com/btrfs-progs-ng/lib/btrfsprogs/btrfsinspect" ) @@ -24,6 +22,7 @@ func maybeSet[K, V comparable](name string, m map[K]V, k K, v V) error { return nil } +/* var maxKey = btrfsprim.Key{ ObjectID: math.MaxUint64, ItemType: math.MaxUint8, @@ -41,6 +40,7 @@ func keyMm(key btrfsprim.Key) btrfsprim.Key { } return key } +*/ func countNodes(nodeScanResults btrfsinspect.ScanDevicesResult) int { var cnt int diff --git a/lib/btrfsprogs/btrfsinspect/rebuildnodes/visualizenodes.go b/lib/btrfsprogs/btrfsinspect/rebuildnodes/visualizenodes.go index 5b1844d..368fafd 100644 --- a/lib/btrfsprogs/btrfsinspect/rebuildnodes/visualizenodes.go +++ b/lib/btrfsprogs/btrfsinspect/rebuildnodes/visualizenodes.go @@ -7,23 +7,18 @@ package rebuildnodes import ( "archive/zip" "context" - "errors" "fmt" "html" "io" - iofs "io/fs" "strings" + "github.com/datawire/dlib/derror" "github.com/datawire/dlib/dlog" "git.lukeshu.com/btrfs-progs-ng/lib/btrfs" "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" - "git.lukeshu.com/btrfs-progs-ng/lib/btrfsprogs/btrfsutil" "git.lukeshu.com/btrfs-progs-ng/lib/containers" - "git.lukeshu.com/btrfs-progs-ng/lib/diskio" "git.lukeshu.com/btrfs-progs-ng/lib/maps" ) @@ -53,166 +48,164 @@ func getCliqueID(cliques map[btrfsprim.ObjID]*containers.Set[btrfsprim.ObjID], t } func VisualizeNodes(ctx context.Context, out io.Writer, fs *btrfs.FS, nodeScanResults btrfsinspect.ScanDevicesResult) error { - uuidMap, err := buildUUIDMap(ctx, fs, nodeScanResults) + scanData, err := ScanDevices(ctx, fs, nodeScanResults) if err != nil { return err } - nfs := &RebuiltTrees{ - inner: fs, - uuidMap: uuidMap, - } - - orphanedNodes, _, treeAncestors, err := classifyNodes(ctx, nfs, nodeScanResults) - if err != nil { - return err - } - - uuidMap.considerAncestors(ctx, treeAncestors) + dlog.Info(ctx, "Walking trees to rebuild root items...") + treeAncestors := getTreeAncestors(*scanData) + scanData.considerAncestors(ctx, treeAncestors) //////////////////////////////////////////////////////////////////////////////////////////// - cliques := getCliques(uuidMap, treeAncestors) + cliques := getCliques(scanData.uuidMap, treeAncestors) dlog.Info(ctx, "Building graphviz graph...") - nodes := make(map[btrfsprim.ObjID]containers.Set[string]) // grouped by treeID - edges := make(map[btrfsprim.ObjID]containers.Set[string]) // grouped by cliqueID - visitedNodes := make(containers.Set[btrfsvol.LogicalAddr]) - var isOrphan bool - - nodeHandler := func(path btrfstree.TreePath, nodeRef *diskio.Ref[btrfsvol.LogicalAddr, btrfstree.Node], err error) error { - addr := path.Node(-1).ToNodeAddr + type graph struct { + nodes map[btrfsprim.ObjID]containers.Set[string] // keyed by treeID + badNodes containers.Set[string] + edges containers.Set[string] + } + graphs := make(map[btrfsprim.ObjID]graph) // keyed by cliqueID + + for _, laddr := range maps.SortedKeys(scanData.Nodes) { + nodeData := scanData.Nodes[laddr] + cliqueID := getCliqueID(cliques, nodeData.Owner) + graph, ok := graphs[cliqueID] + if !ok { + graph.nodes = make(map[btrfsprim.ObjID]containers.Set[string]) + graph.badNodes = make(containers.Set[string]) + graph.edges = make(containers.Set[string]) + } + if graph.nodes[nodeData.Owner] == nil { + graph.nodes[nodeData.Owner] = make(containers.Set[string]) + } - // Node - var treeID btrfsprim.ObjID - var nodeStr string - if err != nil && (errors.Is(err, btrfstree.ErrNotANode) || errors.As(err, new(*btrfstree.IOError))) { - treeID = 0 - nodeStr = fmt.Sprintf(`n%d [shape=star color=red label="%v"]`, addr, addr) + var buf strings.Builder + fmt.Fprintf(&buf, `n%d [shape=record label="%v\ngen=%v\nlvl=%v|{`, + laddr, + laddr, + nodeData.Generation, + nodeData.Level) + if nodeData.NumItems == 0 { + buf.WriteString("(no items)") } else { - treeID = nodeRef.Data.Head.Owner - var buf strings.Builder - fmt.Fprintf(&buf, `n%d [shape=record label="%v\ngen=%v\nlvl=%v|{`, - addr, - nodeRef.Data.Head.Addr, - nodeRef.Data.Head.Generation, - nodeRef.Data.Head.Level) - if nodeRef.Data.Head.NumItems == 0 { - buf.WriteString("(no items)") - } else { - for i := uint32(0); i < nodeRef.Data.Head.NumItems; i++ { - if i == 0 { - fmt.Fprintf(&buf, "%[1]d", i) - } else { - fmt.Fprintf(&buf, "|%[1]d", i) - } + for i := uint32(0); i < nodeData.NumItems; i++ { + if i == 0 { + fmt.Fprintf(&buf, "%[1]d", i) + } else { + fmt.Fprintf(&buf, "|%[1]d", i) } } - buf.WriteString(`}"]`) - nodeStr = buf.String() } - if _, ok := nodes[treeID]; !ok { - nodes[treeID] = make(containers.Set[string]) - nodes[treeID].Insert(fmt.Sprintf(`t%d [label="%s"]`, treeID, html.EscapeString(treeID.String()))) - } - nodes[treeID].Insert(nodeStr) + buf.WriteString(`}"]`) + graph.nodes[nodeData.Owner].Insert(buf.String()) - // Edge - var edge strings.Builder - if len(path) == 1 { - if isOrphan { - edge.WriteString("orphanRoot") - } else { - fmt.Fprintf(&edge, "t%d", path[0].FromTree) - } - } else { - fmt.Fprintf(&edge, "n%d:p%d", path.Node(-2).ToNodeAddr, path.Node(-1).FromItemIdx) - } - fmt.Fprintf(&edge, ` -> n%d [label="`, addr) - if path.Node(-1).FromItemIdx >= 0 { - fmt.Fprintf(&edge, "%d: key=(%d,%v,%d) gen=%v", - path.Node(-1).FromItemIdx, - path.Node(-1).ToKey.ObjectID, - path.Node(-1).ToKey.ItemType, - path.Node(-1).ToKey.Offset, - path.Node(-1).ToNodeGeneration) - } - if err != nil { - fmt.Fprintf(&edge, `\n\n%s" color=red]`, html.EscapeString(err.Error())) - } else { - edge.WriteString(`"]`) + if len(scanData.EdgesTo[laddr]) == 0 { + graph.edges.Insert(fmt.Sprintf("orphanRoot -> n%d", laddr)) } - cliqueID := getCliqueID(cliques, path[0].FromTree) - if treeID != 0 && getCliqueID(cliques, treeID) != cliqueID { - panic(fmt.Errorf("tree %v is not in clique %v", treeID, maps.SortedKeys(*cliques[cliqueID]))) - } - if !cliques[cliqueID].Has(cliqueID) { - panic(fmt.Errorf("clique %v does not contain supposed-member %v", maps.SortedKeys(*cliques[cliqueID]), cliqueID)) + + graphs[cliqueID] = graph + } + + for _, laddr := range maps.SortedKeys(scanData.BadNodes) { + cliqueIDs := make(containers.Set[btrfsprim.ObjID]) + for _, edge := range scanData.EdgesTo[laddr] { + cliqueIDs.Insert(getCliqueID(cliques, edge.FromTree)) } - if _, ok := edges[cliqueID]; !ok { - edges[cliqueID] = make(containers.Set[string]) + if len(cliqueIDs) != 1 { + dlog.Errorf(ctx, "couldn't assign bad node@%v to a clique: %v", laddr, maps.SortedKeys(cliqueIDs)) + continue } - edges[cliqueID].Insert(edge.String()) - // Return - if visitedNodes.Has(addr) { - return iofs.SkipDir - } - visitedNodes.Insert(addr) - return err + cliqueID := cliqueIDs.TakeOne() + graph := graphs[cliqueID] + graph.badNodes.Insert(fmt.Sprintf(`n%d [shape=star color=red label="%v"]`, laddr, laddr)) + graphs[cliqueID] = graph } - walkHandler := btrfstree.TreeWalkHandler{ - Node: func(path btrfstree.TreePath, nodeRef *diskio.Ref[btrfsvol.LogicalAddr, btrfstree.Node]) error { - return nodeHandler(path, nodeRef, nil) - }, - BadNode: func(path btrfstree.TreePath, nodeRef *diskio.Ref[btrfsvol.LogicalAddr, btrfstree.Node], err error) error { - return nodeHandler(path, nodeRef, err) - }, - } + for _, laddr := range maps.SortedKeys(scanData.EdgesFrom) { + for _, kp := range scanData.EdgesFrom[laddr] { + cliqueID := getCliqueID(cliques, kp.FromTree) + graph := graphs[cliqueID] - btrfsutil.WalkAllTrees(ctx, nfs, btrfsutil.WalkAllTreesHandler{ - TreeWalkHandler: walkHandler, - Err: func(err *btrfsutil.WalkError) { - // do nothing - }, - }) - isOrphan = true - for _, potentialRoot := range maps.SortedKeys(orphanedNodes) { - walkFromNode(ctx, nfs, potentialRoot, - func(err *btrfstree.TreeError) { - // do nothing - }, - walkHandler, - ) - } + var buf strings.Builder + if kp.FromNode == 0 { + graph.nodes[kp.FromTree].Insert(fmt.Sprintf(`t%d [label="%s"]`, kp.FromTree, html.EscapeString(kp.FromTree.String()))) + fmt.Fprintf(&buf, "t%d", kp.FromTree) + } else { + fmt.Fprintf(&buf, "n%d", kp.FromNode) + } + fmt.Fprintf(&buf, ` -> n%d [label="%d: key=(%d,%v,%d) gen=%v`, + // dst node + kp.ToNode, + // label + kp.FromItem, + kp.ToKey.ObjectID, + kp.ToKey.ItemType, + kp.ToKey.Offset, + kp.ToGeneration) + toNode, ok := scanData.Nodes[kp.ToNode] + var err error + if !ok { + err = scanData.BadNodes[kp.ToNode] + } else { + var errs derror.MultiError + if toNode.Level != kp.ToLevel { + errs = append(errs, fmt.Errorf("node.level=%v != kp.level=%v", + toNode.Level, kp.ToLevel)) + } + if toNode.Generation != kp.ToGeneration { + errs = append(errs, fmt.Errorf("node.generation=%v != kp.generation=%v", + toNode.Generation, kp.ToGeneration)) + } + if toNode.NumItems == 0 { + errs = append(errs, fmt.Errorf("node.num_items=0")) + } else if toNode.MinItem != kp.ToKey { + errs = append(errs, fmt.Errorf("node.items[0].key=%v != kp.key=%v", + toNode.MinItem, kp.ToKey)) + } + if len(errs) > 0 { + err = errs + } + } + if err != nil { + fmt.Fprintf(&buf, `\n\n%s" color=red]`, html.EscapeString(err.Error())) + } else { + buf.WriteString(`"]`) + } - dlog.Info(ctx, "... done building") + graph.edges.Insert(buf.String()) + graphs[cliqueID] = graph + } + } //////////////////////////////////////////////////////////////////////////////////////////// dlog.Info(ctx, "Writing graphviz output...") - cliqueIDs := maps.SortedKeys(edges) - zw := zip.NewWriter(out) - for _, cliqueID := range cliqueIDs { + for _, cliqueID := range maps.SortedKeys(graphs) { if err := func() (err error) { + graph := graphs[cliqueID] + buf, err := zw.Create(fmt.Sprintf("%d.dot", cliqueID)) if err != nil { return err } - if _, err := fmt.Fprintf(buf, "strict digraph clique%d {\n", cliqueID); err != nil { return err } - clique := cliques[cliqueID] - for _, treeID := range maps.SortedKeys(*clique) { + + for _, treeID := range maps.SortedKeys(graph.nodes) { + nodes := graph.nodes[treeID] + if _, err := fmt.Fprintf(buf, " subgraph cluster_tree%d {\n", treeID); err != nil { return err } - for _, node := range maps.SortedKeys(nodes[treeID]) { + for _, node := range maps.SortedKeys(nodes) { if _, err := fmt.Fprintf(buf, " %s;\n", node); err != nil { return err } @@ -221,15 +214,20 @@ func VisualizeNodes(ctx context.Context, out io.Writer, fs *btrfs.FS, nodeScanRe return err } } - for _, edge := range maps.SortedKeys(edges[cliqueID]) { + for _, node := range maps.SortedKeys(graph.badNodes) { + if _, err := fmt.Fprintf(buf, " %s;\n", node); err != nil { + return err + } + } + for _, edge := range maps.SortedKeys(graph.edges) { if _, err := fmt.Fprintf(buf, " %s;\n", edge); err != nil { return err } } + if _, err := fmt.Fprintln(buf, "}"); err != nil { return err } - return nil }(); err != nil { return err -- cgit v1.2.3-2-g168b