From 66a0058a5c2921b5c4e35732011d32810a9d2f7a Mon Sep 17 00:00:00 2001 From: Luke Shumaker Date: Mon, 29 Aug 2022 21:09:04 -0600 Subject: move things between files --- .../btrfsinspect/rebuildnodes/rebuildnodes.go | 87 --------------- .../btrfsinspect/rebuildnodes/s1_uuidmap.go | 120 +++++++++++++++++++++ .../btrfsinspect/rebuildnodes/s2_lostandfound.go | 105 ++++++++++++++++++ .../btrfsinspect/rebuildnodes/uuidmap.go | 120 --------------------- 4 files changed, 225 insertions(+), 207 deletions(-) create mode 100644 lib/btrfsprogs/btrfsinspect/rebuildnodes/s1_uuidmap.go create mode 100644 lib/btrfsprogs/btrfsinspect/rebuildnodes/s2_lostandfound.go delete mode 100644 lib/btrfsprogs/btrfsinspect/rebuildnodes/uuidmap.go (limited to 'lib') diff --git a/lib/btrfsprogs/btrfsinspect/rebuildnodes/rebuildnodes.go b/lib/btrfsprogs/btrfsinspect/rebuildnodes/rebuildnodes.go index 7950393..e5ae5e4 100644 --- a/lib/btrfsprogs/btrfsinspect/rebuildnodes/rebuildnodes.go +++ b/lib/btrfsprogs/btrfsinspect/rebuildnodes/rebuildnodes.go @@ -6,12 +6,10 @@ package rebuildnodes import ( "context" - "errors" "fmt" iofs "io/fs" "math" "sort" - "strings" "github.com/datawire/dlib/dlog" @@ -135,91 +133,6 @@ func countNodes(nodeScanResults btrfsinspect.ScanDevicesResult) int { return cnt } -func lostAndFoundNodes(ctx context.Context, fs _FS, nodeScanResults btrfsinspect.ScanDevicesResult) (map[btrfsvol.LogicalAddr]struct{}, error) { - lastPct := -1 - total := countNodes(nodeScanResults) - progress := func(done int) { - pct := int(100 * float64(done) / float64(total)) - if pct != lastPct || done == total { - dlog.Infof(ctx, "... %v%% (%v/%v)", - pct, done, total) - lastPct = pct - } - } - - attachedNodes := make(map[btrfsvol.LogicalAddr]struct{}) - btrfsutil.WalkAllTrees(ctx, fs, btrfsutil.WalkAllTreesHandler{ - TreeWalkHandler: btrfstree.TreeWalkHandler{ - Node: func(path btrfstree.TreePath, _ *diskio.Ref[btrfsvol.LogicalAddr, btrfstree.Node]) error { - addr := path.Node(-1).ToNodeAddr - if _, alreadyVisited := attachedNodes[addr]; alreadyVisited { - // Can happen because of COW subvolumes; - // this is really a DAG not a tree. - return iofs.SkipDir - } - attachedNodes[addr] = struct{}{} - progress(len(attachedNodes)) - return nil - }, - }, - Err: func(err *btrfsutil.WalkError) { - // do nothing - if !errors.Is(err, btrfstree.ErrNotANode) && !strings.Contains(err.Error(), "read: could not map logical address") { - dlog.Errorf(ctx, "dbg walk err: %v", err) - } - }, - }) - - orphanedNodes := make(map[btrfsvol.LogicalAddr]int) - for _, devResults := range nodeScanResults { - for laddr := range devResults.FoundNodes { - if _, attached := attachedNodes[laddr]; !attached { - orphanedNodes[laddr] = 0 - } - } - } - dlog.Infof(ctx, - "... (finished processing %v attached nodes, proceeding to process %v lost nodes, for a total of %v)", - len(attachedNodes), len(orphanedNodes), len(attachedNodes)+len(orphanedNodes)) - - // 'orphanedRoots' is a subset of 'orphanedNodes'; start with - // it as the complete orphanedNodes, and then remove entries. - orphanedRoots := make(map[btrfsvol.LogicalAddr]struct{}, len(orphanedNodes)) - for node := range orphanedNodes { - orphanedRoots[node] = struct{}{} - } - done := len(attachedNodes) - for potentialRoot := range orphanedRoots { - done++ - progress(done) - if orphanedNodes[potentialRoot] > 1 { - continue - } - walkCtx, cancel := context.WithCancel(ctx) - walkFromNode(walkCtx, fs, potentialRoot, - func(err *btrfstree.TreeError) { - // do nothing - }, - btrfstree.TreeWalkHandler{ - PreNode: func(path btrfstree.TreePath) error { - nodeAddr := path.Node(-1).ToNodeAddr - if nodeAddr != potentialRoot { - delete(orphanedRoots, nodeAddr) - } - visitCnt := orphanedNodes[nodeAddr] + 1 - orphanedNodes[nodeAddr] = visitCnt - if visitCnt > 1 { - cancel() - } - return nil - }, - }, - ) - } - - return orphanedRoots, nil -} - func getChunkTreeUUID(ctx context.Context, fs _FS) (btrfsprim.UUID, bool) { ctx, cancel := context.WithCancel(ctx) var ret btrfsprim.UUID diff --git a/lib/btrfsprogs/btrfsinspect/rebuildnodes/s1_uuidmap.go b/lib/btrfsprogs/btrfsinspect/rebuildnodes/s1_uuidmap.go new file mode 100644 index 0000000..ba090fb --- /dev/null +++ b/lib/btrfsprogs/btrfsinspect/rebuildnodes/s1_uuidmap.go @@ -0,0 +1,120 @@ +// Copyright (C) 2022 Luke Shumaker +// +// SPDX-License-Identifier: GPL-2.0-or-later + +package rebuildnodes + +import ( + "context" + "fmt" + + "github.com/datawire/dlib/dlog" + + "git.lukeshu.com/btrfs-progs-ng/lib/btrfs" + "git.lukeshu.com/btrfs-progs-ng/lib/btrfs/btrfsitem" + "git.lukeshu.com/btrfs-progs-ng/lib/btrfs/btrfsprim" + "git.lukeshu.com/btrfs-progs-ng/lib/btrfs/btrfstree" + "git.lukeshu.com/btrfs-progs-ng/lib/btrfs/btrfsvol" + "git.lukeshu.com/btrfs-progs-ng/lib/btrfsprogs/btrfsinspect" + "git.lukeshu.com/btrfs-progs-ng/lib/containers" + "git.lukeshu.com/btrfs-progs-ng/lib/maps" +) + +type uuidMap struct { + ObjID2UUID map[btrfsprim.ObjID]btrfsprim.UUID + UUID2ObjID map[btrfsprim.UUID]btrfsprim.ObjID + TreeParent map[btrfsprim.ObjID]btrfsprim.UUID +} + +func maybeSet[K, V comparable](name string, m map[K]V, k K, v V) error { + if other, conflict := m[k]; conflict && other != v { + return fmt.Errorf("conflict: %s %v can't have both %v and %v", name, k, other, v) + } + m[k] = v + return nil +} + +func buildUUIDMap(ctx context.Context, fs *btrfs.FS, scanResults btrfsinspect.ScanDevicesResult) (uuidMap, error) { + dlog.Infof(ctx, "Building table of ObjID←→UUID...") + + sb, err := fs.Superblock() + if err != nil { + return uuidMap{}, nil + } + + lastPct := -1 + total := countNodes(scanResults) + done := 0 + progress := func() { + pct := int(100 * float64(done) / float64(total)) + if pct != lastPct || done == total { + dlog.Infof(ctx, "... %v%% (%v/%v)", + pct, done, total) + lastPct = pct + } + } + + ret := uuidMap{ + ObjID2UUID: make(map[btrfsprim.ObjID]btrfsprim.UUID), + UUID2ObjID: make(map[btrfsprim.UUID]btrfsprim.ObjID), + TreeParent: make(map[btrfsprim.ObjID]btrfsprim.UUID), + } + seenTreeIDs := make(map[btrfsprim.ObjID]struct{}) + + progress() + for _, devResults := range scanResults { + for laddr := range devResults.FoundNodes { + nodeRef, err := btrfstree.ReadNode[btrfsvol.LogicalAddr](fs, *sb, laddr, btrfstree.NodeExpectations{ + LAddr: containers.Optional[btrfsvol.LogicalAddr]{OK: true, Val: laddr}, + }) + if err != nil { + return uuidMap{}, nil + } + for _, item := range nodeRef.Data.BodyLeaf { + switch itemBody := item.Body.(type) { + case btrfsitem.Root: + if err := maybeSet("ObjID2UUID", ret.ObjID2UUID, item.Key.ObjectID, itemBody.UUID); err != nil { + return uuidMap{}, err + } + if itemBody.UUID != (btrfsprim.UUID{}) { + if err := maybeSet("UUID2ObjID", ret.UUID2ObjID, itemBody.UUID, item.Key.ObjectID); err != nil { + return uuidMap{}, err + } + } + if err := maybeSet("ParentUUID", ret.TreeParent, item.Key.ObjectID, itemBody.ParentUUID); err != nil { + return uuidMap{}, err + } + case btrfsitem.UUIDMap: + uuid := btrfsitem.KeyToUUID(item.Key) + if err := maybeSet("ObjID2UUID", ret.ObjID2UUID, itemBody.ObjID, uuid); err != nil { + return uuidMap{}, err + } + if err := maybeSet("UUID2ObjID", ret.UUID2ObjID, uuid, itemBody.ObjID); err != nil { + return uuidMap{}, err + } + } + } + seenTreeIDs[nodeRef.Data.Head.Owner] = struct{}{} + done++ + progress() + } + } + progress() + + missing := make(map[btrfsprim.ObjID]struct{}) + for treeID := range seenTreeIDs { + if _, ok := ret.ObjID2UUID[treeID]; !ok && treeID != btrfsprim.ROOT_TREE_OBJECTID { + missing[treeID] = struct{}{} + continue + } + if _, ok := ret.TreeParent[treeID]; !ok && treeID >= btrfsprim.FIRST_FREE_OBJECTID && treeID <= btrfsprim.LAST_FREE_OBJECTID { + missing[treeID] = struct{}{} + } + } + if len(missing) > 0 { + dlog.Errorf(ctx, "... could not find root items for %d trees: %v", len(missing), maps.SortedKeys(missing)) + } + + dlog.Info(ctx, "... done building table") + return ret, nil +} diff --git a/lib/btrfsprogs/btrfsinspect/rebuildnodes/s2_lostandfound.go b/lib/btrfsprogs/btrfsinspect/rebuildnodes/s2_lostandfound.go new file mode 100644 index 0000000..8da8588 --- /dev/null +++ b/lib/btrfsprogs/btrfsinspect/rebuildnodes/s2_lostandfound.go @@ -0,0 +1,105 @@ +// Copyright (C) 2022 Luke Shumaker +// +// SPDX-License-Identifier: GPL-2.0-or-later + +package rebuildnodes + +import ( + "context" + "errors" + iofs "io/fs" + "strings" + + "github.com/datawire/dlib/dlog" + + "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 lostAndFoundNodes(ctx context.Context, fs _FS, nodeScanResults btrfsinspect.ScanDevicesResult) (map[btrfsvol.LogicalAddr]struct{}, error) { + lastPct := -1 + total := countNodes(nodeScanResults) + progress := func(done int) { + pct := int(100 * float64(done) / float64(total)) + if pct != lastPct || done == total { + dlog.Infof(ctx, "... %v%% (%v/%v)", + pct, done, total) + lastPct = pct + } + } + + attachedNodes := make(map[btrfsvol.LogicalAddr]struct{}) + btrfsutil.WalkAllTrees(ctx, fs, btrfsutil.WalkAllTreesHandler{ + TreeWalkHandler: btrfstree.TreeWalkHandler{ + Node: func(path btrfstree.TreePath, _ *diskio.Ref[btrfsvol.LogicalAddr, btrfstree.Node]) error { + addr := path.Node(-1).ToNodeAddr + if _, alreadyVisited := attachedNodes[addr]; alreadyVisited { + // Can happen because of COW subvolumes; + // this is really a DAG not a tree. + return iofs.SkipDir + } + attachedNodes[addr] = struct{}{} + progress(len(attachedNodes)) + return nil + }, + }, + Err: func(err *btrfsutil.WalkError) { + // do nothing + if !errors.Is(err, btrfstree.ErrNotANode) && !strings.Contains(err.Error(), "read: could not map logical address") { + dlog.Errorf(ctx, "dbg walk err: %v", err) + } + }, + }) + + orphanedNodes := make(map[btrfsvol.LogicalAddr]int) + for _, devResults := range nodeScanResults { + for laddr := range devResults.FoundNodes { + if _, attached := attachedNodes[laddr]; !attached { + orphanedNodes[laddr] = 0 + } + } + } + dlog.Infof(ctx, + "... (finished processing %v attached nodes, proceeding to process %v lost nodes, for a total of %v)", + len(attachedNodes), len(orphanedNodes), len(attachedNodes)+len(orphanedNodes)) + + // 'orphanedRoots' is a subset of 'orphanedNodes'; start with + // it as the complete orphanedNodes, and then remove entries. + orphanedRoots := make(map[btrfsvol.LogicalAddr]struct{}, len(orphanedNodes)) + for node := range orphanedNodes { + orphanedRoots[node] = struct{}{} + } + done := len(attachedNodes) + for potentialRoot := range orphanedRoots { + done++ + progress(done) + if orphanedNodes[potentialRoot] > 1 { + continue + } + walkCtx, cancel := context.WithCancel(ctx) + walkFromNode(walkCtx, fs, potentialRoot, + func(err *btrfstree.TreeError) { + // do nothing + }, + btrfstree.TreeWalkHandler{ + PreNode: func(path btrfstree.TreePath) error { + nodeAddr := path.Node(-1).ToNodeAddr + if nodeAddr != potentialRoot { + delete(orphanedRoots, nodeAddr) + } + visitCnt := orphanedNodes[nodeAddr] + 1 + orphanedNodes[nodeAddr] = visitCnt + if visitCnt > 1 { + cancel() + } + return nil + }, + }, + ) + } + + return orphanedRoots, nil +} diff --git a/lib/btrfsprogs/btrfsinspect/rebuildnodes/uuidmap.go b/lib/btrfsprogs/btrfsinspect/rebuildnodes/uuidmap.go deleted file mode 100644 index ba090fb..0000000 --- a/lib/btrfsprogs/btrfsinspect/rebuildnodes/uuidmap.go +++ /dev/null @@ -1,120 +0,0 @@ -// Copyright (C) 2022 Luke Shumaker -// -// SPDX-License-Identifier: GPL-2.0-or-later - -package rebuildnodes - -import ( - "context" - "fmt" - - "github.com/datawire/dlib/dlog" - - "git.lukeshu.com/btrfs-progs-ng/lib/btrfs" - "git.lukeshu.com/btrfs-progs-ng/lib/btrfs/btrfsitem" - "git.lukeshu.com/btrfs-progs-ng/lib/btrfs/btrfsprim" - "git.lukeshu.com/btrfs-progs-ng/lib/btrfs/btrfstree" - "git.lukeshu.com/btrfs-progs-ng/lib/btrfs/btrfsvol" - "git.lukeshu.com/btrfs-progs-ng/lib/btrfsprogs/btrfsinspect" - "git.lukeshu.com/btrfs-progs-ng/lib/containers" - "git.lukeshu.com/btrfs-progs-ng/lib/maps" -) - -type uuidMap struct { - ObjID2UUID map[btrfsprim.ObjID]btrfsprim.UUID - UUID2ObjID map[btrfsprim.UUID]btrfsprim.ObjID - TreeParent map[btrfsprim.ObjID]btrfsprim.UUID -} - -func maybeSet[K, V comparable](name string, m map[K]V, k K, v V) error { - if other, conflict := m[k]; conflict && other != v { - return fmt.Errorf("conflict: %s %v can't have both %v and %v", name, k, other, v) - } - m[k] = v - return nil -} - -func buildUUIDMap(ctx context.Context, fs *btrfs.FS, scanResults btrfsinspect.ScanDevicesResult) (uuidMap, error) { - dlog.Infof(ctx, "Building table of ObjID←→UUID...") - - sb, err := fs.Superblock() - if err != nil { - return uuidMap{}, nil - } - - lastPct := -1 - total := countNodes(scanResults) - done := 0 - progress := func() { - pct := int(100 * float64(done) / float64(total)) - if pct != lastPct || done == total { - dlog.Infof(ctx, "... %v%% (%v/%v)", - pct, done, total) - lastPct = pct - } - } - - ret := uuidMap{ - ObjID2UUID: make(map[btrfsprim.ObjID]btrfsprim.UUID), - UUID2ObjID: make(map[btrfsprim.UUID]btrfsprim.ObjID), - TreeParent: make(map[btrfsprim.ObjID]btrfsprim.UUID), - } - seenTreeIDs := make(map[btrfsprim.ObjID]struct{}) - - progress() - for _, devResults := range scanResults { - for laddr := range devResults.FoundNodes { - nodeRef, err := btrfstree.ReadNode[btrfsvol.LogicalAddr](fs, *sb, laddr, btrfstree.NodeExpectations{ - LAddr: containers.Optional[btrfsvol.LogicalAddr]{OK: true, Val: laddr}, - }) - if err != nil { - return uuidMap{}, nil - } - for _, item := range nodeRef.Data.BodyLeaf { - switch itemBody := item.Body.(type) { - case btrfsitem.Root: - if err := maybeSet("ObjID2UUID", ret.ObjID2UUID, item.Key.ObjectID, itemBody.UUID); err != nil { - return uuidMap{}, err - } - if itemBody.UUID != (btrfsprim.UUID{}) { - if err := maybeSet("UUID2ObjID", ret.UUID2ObjID, itemBody.UUID, item.Key.ObjectID); err != nil { - return uuidMap{}, err - } - } - if err := maybeSet("ParentUUID", ret.TreeParent, item.Key.ObjectID, itemBody.ParentUUID); err != nil { - return uuidMap{}, err - } - case btrfsitem.UUIDMap: - uuid := btrfsitem.KeyToUUID(item.Key) - if err := maybeSet("ObjID2UUID", ret.ObjID2UUID, itemBody.ObjID, uuid); err != nil { - return uuidMap{}, err - } - if err := maybeSet("UUID2ObjID", ret.UUID2ObjID, uuid, itemBody.ObjID); err != nil { - return uuidMap{}, err - } - } - } - seenTreeIDs[nodeRef.Data.Head.Owner] = struct{}{} - done++ - progress() - } - } - progress() - - missing := make(map[btrfsprim.ObjID]struct{}) - for treeID := range seenTreeIDs { - if _, ok := ret.ObjID2UUID[treeID]; !ok && treeID != btrfsprim.ROOT_TREE_OBJECTID { - missing[treeID] = struct{}{} - continue - } - if _, ok := ret.TreeParent[treeID]; !ok && treeID >= btrfsprim.FIRST_FREE_OBJECTID && treeID <= btrfsprim.LAST_FREE_OBJECTID { - missing[treeID] = struct{}{} - } - } - if len(missing) > 0 { - dlog.Errorf(ctx, "... could not find root items for %d trees: %v", len(missing), maps.SortedKeys(missing)) - } - - dlog.Info(ctx, "... done building table") - return ret, nil -} -- cgit v1.2.3-2-g168b