From 8c8c6c27552f8554ba014c34d684cb90538ef65b Mon Sep 17 00:00:00 2001 From: Luke Shumaker Date: Tue, 28 Feb 2023 14:05:27 -0700 Subject: Move files around [ci-skip] --- lib/btrfsutil/rebuilt_forrest.go | 208 +++++++++++++++++++++++++++++++++++++++ 1 file changed, 208 insertions(+) create mode 100644 lib/btrfsutil/rebuilt_forrest.go (limited to 'lib/btrfsutil/rebuilt_forrest.go') diff --git a/lib/btrfsutil/rebuilt_forrest.go b/lib/btrfsutil/rebuilt_forrest.go new file mode 100644 index 0000000..dbbc6eb --- /dev/null +++ b/lib/btrfsutil/rebuilt_forrest.go @@ -0,0 +1,208 @@ +// Copyright (C) 2022-2023 Luke Shumaker +// +// SPDX-License-Identifier: GPL-2.0-or-later + +package btrees + +import ( + "context" + + "github.com/datawire/dlib/dlog" + + "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" + 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/slices" + "git.lukeshu.com/btrfs-progs-ng/lib/textui" +) + +type Callbacks interface { + AddedItem(ctx context.Context, tree btrfsprim.ObjID, key btrfsprim.Key) + AddedRoot(ctx context.Context, tree btrfsprim.ObjID, root btrfsvol.LogicalAddr) + LookupRoot(ctx context.Context, tree btrfsprim.ObjID) (offset btrfsprim.Generation, item btrfsitem.Root, ok bool) + LookupUUID(ctx context.Context, uuid btrfsprim.UUID) (id btrfsprim.ObjID, ok bool) +} + +// RebuiltForrest is an abstraction for rebuilding and accessing +// potentially broken btrees. +// +// It is conceptually a btrfstree.TreeOperator, and adds similar +// broken-tree handling to btrfsutil.BrokenForrest. However, the API +// is different thant btrfstree.TreeOperator, and is much more +// efficient than btrfsutil.BrokenForrest. +// +// The efficiency improvements are possible because of the API +// differences, which are necessary for how it is used in +// rebuildnodes: +// +// - it consumes an already-read graph.Graph instead of reading the +// graph itself +// +// - it does not use `btrfstree.TreePath` +// +// - it does not keep track of errors encountered in a tree +// +// Additionally, it provides some functionality that +// btrfsutil.BrokenForrest does not: +// +// - it provides a .LeafToRoots() method to advise on what +// additional roots should be added +// +// - it provides a .COWDistance() method to compare how related two +// trees are +// +// A zero RebuiltForrest is invalid; it must be initialized with +// NewRebuiltForrest(). +type RebuiltForrest struct { + // static + sb btrfstree.Superblock + graph pkggraph.Graph + keyIO *keyio.Handle + cb Callbacks + + // mutable + treesMu nestedMutex + trees map[btrfsprim.ObjID]*RebuiltTree // must hold .treesMu to access + leafs containers.ARCache[btrfsprim.ObjID, map[btrfsvol.LogicalAddr]containers.Set[btrfsvol.LogicalAddr]] + incItems containers.ARCache[btrfsprim.ObjID, *itemIndex] + excItems containers.ARCache[btrfsprim.ObjID, *itemIndex] +} + +// NewRebuiltForrest returns a new RebuiltForrest instance. All of +// the callbacks must be non-nil. +func NewRebuiltForrest(sb btrfstree.Superblock, graph pkggraph.Graph, keyIO *keyio.Handle, cb Callbacks) *RebuiltForrest { + return &RebuiltForrest{ + sb: sb, + graph: graph, + keyIO: keyIO, + cb: cb, + + trees: make(map[btrfsprim.ObjID]*RebuiltTree), + leafs: containers.ARCache[btrfsprim.ObjID, map[btrfsvol.LogicalAddr]containers.Set[btrfsvol.LogicalAddr]]{ + MaxLen: textui.Tunable(8), + }, + incItems: containers.ARCache[btrfsprim.ObjID, *itemIndex]{ + MaxLen: textui.Tunable(8), + }, + excItems: containers.ARCache[btrfsprim.ObjID, *itemIndex]{ + MaxLen: textui.Tunable(8), + }, + } +} + +// Tree returns a given tree, initializing it if nescessary. If it is +// unable to initialize the tree, then nil is returned, and nothing is +// done to the forrest. +// +// The tree is initialized with the normal root node of the tree. +func (ts *RebuiltForrest) Tree(ctx context.Context, treeID btrfsprim.ObjID) *RebuiltTree { + ctx = ts.treesMu.Lock(ctx) + defer ts.treesMu.Unlock() + if !ts.addTree(ctx, treeID, nil) { + return nil + } + return ts.trees[treeID] +} + +func (ts *RebuiltForrest) addTree(ctx context.Context, treeID btrfsprim.ObjID, stack []btrfsprim.ObjID) (ok bool) { + if tree, ok := ts.trees[treeID]; ok { + return tree != nil + } + defer func() { + if !ok { + // Store a negative cache of this. tree.AddRoot() for the ROOT or UUID + // trees will call .flushNegativeCache(). + ts.trees[treeID] = nil + } + }() + stack = append(stack, treeID) + ctx = dlog.WithField(ctx, "btrfsinspect.rebuild-nodes.rebuild.add-tree", stack) + dlog.Info(ctx, "adding tree...") + if slices.Contains(treeID, stack[:len(stack)-1]) { + dlog.Errorf(ctx, "failed to add tree: loop detected: %v", stack) + return false + } + + tree := &RebuiltTree{ + ID: treeID, + Roots: make(containers.Set[btrfsvol.LogicalAddr]), + forrest: ts, + } + var root btrfsvol.LogicalAddr + switch treeID { + case btrfsprim.ROOT_TREE_OBJECTID: + root = ts.sb.RootTree + case btrfsprim.CHUNK_TREE_OBJECTID: + root = ts.sb.ChunkTree + case btrfsprim.TREE_LOG_OBJECTID: + root = ts.sb.LogTree + case btrfsprim.BLOCK_GROUP_TREE_OBJECTID: + root = ts.sb.BlockGroupRoot + default: + if !ts.addTree(ctx, btrfsprim.ROOT_TREE_OBJECTID, stack) { + dlog.Error(ctx, "failed to add tree: add ROOT_TREE") + return false + } + rootOff, rootItem, ok := ts.cb.LookupRoot(ctx, treeID) + if !ok { + dlog.Error(ctx, "failed to add tree: lookup ROOT_ITEM") + return false + } + root = rootItem.ByteNr + tree.UUID = rootItem.UUID + if rootItem.ParentUUID != (btrfsprim.UUID{}) { + tree.ParentGen = rootOff + if !ts.addTree(ctx, btrfsprim.UUID_TREE_OBJECTID, stack) { + return false + } + parentID, ok := ts.cb.LookupUUID(ctx, rootItem.ParentUUID) + if !ok { + dlog.Error(ctx, "failed to add tree: lookup UUID") + return false + } + if !ts.addTree(ctx, parentID, stack) { + dlog.Error(ctx, "failed to add tree: add parent tree") + return false + } + tree.Parent = ts.trees[parentID] + } + } + + ts.trees[treeID] = tree + if root != 0 { + tree.AddRoot(ctx, root) + } + + return true +} + +func (ts *RebuiltForrest) flushNegativeCache(ctx context.Context) { + _ = ts.treesMu.Lock(ctx) + defer ts.treesMu.Unlock() + for treeID, tree := range ts.trees { + if tree == nil { + delete(ts.trees, treeID) + } + } +} + +// ListRoots returns a listing of all initialized trees and their root +// nodes. +// +// Do not mutate the set of roots for a tree; it is a pointer to the +// RebuiltForrest's internal set! +func (ts *RebuiltForrest) ListRoots(ctx context.Context) map[btrfsprim.ObjID]containers.Set[btrfsvol.LogicalAddr] { + _ = ts.treesMu.Lock(ctx) + defer ts.treesMu.Unlock() + ret := make(map[btrfsprim.ObjID]containers.Set[btrfsvol.LogicalAddr]) + for treeID, tree := range ts.trees { + if tree != nil { + ret[treeID] = tree.Roots + } + } + return ret +} -- cgit v1.2.3-2-g168b From 1be85fecedebe9ea37b910a15a5c45dd2e57649d Mon Sep 17 00:00:00 2001 From: Luke Shumaker Date: Sun, 12 Mar 2023 15:17:39 -0600 Subject: Get it to compile with the renamed files #!/bin/bash set -e git ls-files :*.go :!tools/| while read -r file; do pkgname=${file%/*.go} pkgname=${pkgname##*/} if [[ "$pkgname" == btrfs-rec ]]; then pkgname=main fi sed -i "s/^package [^_]*/package ${pkgname}/" "$file" done # btrfsutil #################################################################### gofmt -w -r 'rebuildnodes -> rebuildtrees' cmd lib gofmt -w -r 'btrees -> btrfsutil' cmd lib gofmt -w -r 'keyio -> btrfsutil' cmd lib sed -i 's/func New/func NewGraph/' lib/btrfsutil/graph.go gofmt -w -r 'graph.New -> btrfsutil.NewGraph' cmd lib gofmt -w -r 'graph.Graph -> btrfsutil.Graph' cmd lib sed -i -e '/\/graph"/d' -e 's/pkggraph\.//' lib/btrfsutil/rebuilt_forrest.go gofmt -w -r 'btrfsutil.BrokenForrest -> BrokenForrest ' lib/btrfsutil gofmt -w -r 'btrfsutil.Handle -> Handle ' lib/btrfsutil gofmt -w -r 'btrfsutil.Graph -> Graph ' lib/btrfsutil gofmt -w -r 'btrfsutil.ItemPtr -> ItemPtr ' lib/btrfsutil gofmt -w -r 'Handle -> KeyIO' lib/btrfsutil gofmt -w -r 'btrfsutil.Handle -> btrfsutil.KeyIO' cmd/btrfs-rec/inspect/rebuildtrees/ gofmt -w -r 'NewHandle -> NewKeyIO' cmd lib # rebuildmappings ############################################################## gofmt -w -r 'btrfsinspect.DumpTrees -> dumptrees.DumpTrees' cmd lib gofmt -w -r 'btrfsinspect.MountRO -> mount.MountRO' cmd lib gofmt -w -r 'btrfsinspect.ScanDevices -> rebuildmappings.ScanDevices' cmd lib gofmt -w -r 'btrfsinspect.ScanDevicesResult -> rebuildmappings.ScanDevicesResult' cmd lib gofmt -w -r 'btrfsinspect.SysExtentCSum -> rebuildmappings.SysExtentCSum' cmd lib gofmt -w -r 'rebuildmappings.IndexAll -> IndexAll ' cmd/btrfs-rec/inspect/rebuildmappings gofmt -w -r 'rebuildmappings.ScanDevicesResult -> ScanDevicesResult ' cmd/btrfs-rec/inspect/rebuildmappings gofmt -w -r 'rebuildmappings.SysExtentCSum -> SysExtentCSum ' cmd/btrfs-rec/inspect/rebuildmappings # btrfscheck ################################################################### sed -i -e 's/func handle/func Handle/' lib/btrfscheck/graph.go sed -i 's/handle/btrfscheck.Handle/g' cmd/btrfs-rec/inspect/rebuildtrees/rebuild.go gofmt -w -r 'fsErr -> FSErr ' lib/btrfscheck cmd/btrfs-rec/inspect/rebuildtrees gofmt -w -r 'want -> Want ' lib/btrfscheck cmd/btrfs-rec/inspect/rebuildtrees gofmt -w -r 'wantOff -> WantOff ' lib/btrfscheck cmd/btrfs-rec/inspect/rebuildtrees gofmt -w -r 'wantDirIndex -> WantDirIndex ' lib/btrfscheck cmd/btrfs-rec/inspect/rebuildtrees gofmt -w -r 'wantCSum -> WantCSum ' lib/btrfscheck cmd/btrfs-rec/inspect/rebuildtrees gofmt -w -r 'wantFileExt -> WantFileExt ' lib/btrfscheck cmd/btrfs-rec/inspect/rebuildtrees # generic imports ############################################################## replace() { git grep -l "$1"|xargs -r sed -i "s,$1,$2,g" } replace 'lib/btrfsprogs/btrfsinspect/rebuildmappings"' 'cmd/btrfs-rec/inspect/rebuildmappings"' replace 'lib/btrfsprogs/btrfsinspect/rebuildnodes"' 'cmd/btrfs-rec/inspect/rebuildtrees"' replace 'lib/btrfsprogs/btrfsutil"' 'lib/btrfsutil"' goimports -w cmd lib ./tools/bin/golangci-lint run --fix ./... And then touch-up copyright statements by hand. --- lib/btrfsutil/rebuilt_forrest.go | 10 ++++------ 1 file changed, 4 insertions(+), 6 deletions(-) (limited to 'lib/btrfsutil/rebuilt_forrest.go') diff --git a/lib/btrfsutil/rebuilt_forrest.go b/lib/btrfsutil/rebuilt_forrest.go index dbbc6eb..8d4b810 100644 --- a/lib/btrfsutil/rebuilt_forrest.go +++ b/lib/btrfsutil/rebuilt_forrest.go @@ -2,7 +2,7 @@ // // SPDX-License-Identifier: GPL-2.0-or-later -package btrees +package btrfsutil import ( "context" @@ -13,8 +13,6 @@ import ( "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" - 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/slices" "git.lukeshu.com/btrfs-progs-ng/lib/textui" @@ -60,8 +58,8 @@ type Callbacks interface { type RebuiltForrest struct { // static sb btrfstree.Superblock - graph pkggraph.Graph - keyIO *keyio.Handle + graph Graph + keyIO *KeyIO cb Callbacks // mutable @@ -74,7 +72,7 @@ type RebuiltForrest struct { // NewRebuiltForrest returns a new RebuiltForrest instance. All of // the callbacks must be non-nil. -func NewRebuiltForrest(sb btrfstree.Superblock, graph pkggraph.Graph, keyIO *keyio.Handle, cb Callbacks) *RebuiltForrest { +func NewRebuiltForrest(sb btrfstree.Superblock, graph Graph, keyIO *KeyIO, cb Callbacks) *RebuiltForrest { return &RebuiltForrest{ sb: sb, graph: graph, -- cgit v1.2.3-2-g168b From 84099499feb558a01253bd272563fa1271527a75 Mon Sep 17 00:00:00 2001 From: Luke Shumaker Date: Sun, 12 Mar 2023 17:09:51 -0600 Subject: Update identifiers and comments to reflect new file/package names --- lib/btrfsutil/rebuilt_forrest.go | 22 +++++++++++----------- 1 file changed, 11 insertions(+), 11 deletions(-) (limited to 'lib/btrfsutil/rebuilt_forrest.go') diff --git a/lib/btrfsutil/rebuilt_forrest.go b/lib/btrfsutil/rebuilt_forrest.go index 8d4b810..3dfb24c 100644 --- a/lib/btrfsutil/rebuilt_forrest.go +++ b/lib/btrfsutil/rebuilt_forrest.go @@ -18,7 +18,7 @@ import ( "git.lukeshu.com/btrfs-progs-ng/lib/textui" ) -type Callbacks interface { +type RebuiltForrestCallbacks interface { AddedItem(ctx context.Context, tree btrfsprim.ObjID, key btrfsprim.Key) AddedRoot(ctx context.Context, tree btrfsprim.ObjID, root btrfsvol.LogicalAddr) LookupRoot(ctx context.Context, tree btrfsprim.ObjID) (offset btrfsprim.Generation, item btrfsitem.Root, ok bool) @@ -29,23 +29,23 @@ type Callbacks interface { // potentially broken btrees. // // It is conceptually a btrfstree.TreeOperator, and adds similar -// broken-tree handling to btrfsutil.BrokenForrest. However, the API -// is different thant btrfstree.TreeOperator, and is much more -// efficient than btrfsutil.BrokenForrest. +// broken-tree handling to OldRebuiltForrest. However, the API is +// different than btrfstree.TreeOperator, and is much more efficient +// than OldRebuiltForrest. // // The efficiency improvements are possible because of the API // differences, which are necessary for how it is used in -// rebuildnodes: +// rebuildtrees: // -// - it consumes an already-read graph.Graph instead of reading the -// graph itself +// - it consumes an already-read Graph instead of reading the graph +// itself // // - it does not use `btrfstree.TreePath` // // - it does not keep track of errors encountered in a tree // -// Additionally, it provides some functionality that -// btrfsutil.BrokenForrest does not: +// Additionally, it provides some functionality that OldRebuiltForrest +// does not: // // - it provides a .LeafToRoots() method to advise on what // additional roots should be added @@ -60,7 +60,7 @@ type RebuiltForrest struct { sb btrfstree.Superblock graph Graph keyIO *KeyIO - cb Callbacks + cb RebuiltForrestCallbacks // mutable treesMu nestedMutex @@ -72,7 +72,7 @@ type RebuiltForrest struct { // NewRebuiltForrest returns a new RebuiltForrest instance. All of // the callbacks must be non-nil. -func NewRebuiltForrest(sb btrfstree.Superblock, graph Graph, keyIO *KeyIO, cb Callbacks) *RebuiltForrest { +func NewRebuiltForrest(sb btrfstree.Superblock, graph Graph, keyIO *KeyIO, cb RebuiltForrestCallbacks) *RebuiltForrest { return &RebuiltForrest{ sb: sb, graph: graph, -- cgit v1.2.3-2-g168b From e92796fed05143239733d3feec0231a69af2f617 Mon Sep 17 00:00:00 2001 From: Luke Shumaker Date: Sun, 12 Mar 2023 17:09:41 -0600 Subject: Update log field names to reflect new file/package names --- lib/btrfsutil/rebuilt_forrest.go | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) (limited to 'lib/btrfsutil/rebuilt_forrest.go') diff --git a/lib/btrfsutil/rebuilt_forrest.go b/lib/btrfsutil/rebuilt_forrest.go index 3dfb24c..70ece13 100644 --- a/lib/btrfsutil/rebuilt_forrest.go +++ b/lib/btrfsutil/rebuilt_forrest.go @@ -118,7 +118,7 @@ func (ts *RebuiltForrest) addTree(ctx context.Context, treeID btrfsprim.ObjID, s } }() stack = append(stack, treeID) - ctx = dlog.WithField(ctx, "btrfsinspect.rebuild-nodes.rebuild.add-tree", stack) + ctx = dlog.WithField(ctx, "btrfs.util.rebuilt-forrest.add-tree", stack) dlog.Info(ctx, "adding tree...") if slices.Contains(treeID, stack[:len(stack)-1]) { dlog.Errorf(ctx, "failed to add tree: loop detected: %v", stack) -- cgit v1.2.3-2-g168b