From 504c3695c7dae682504335a47e1f0f873f95ca30 Mon Sep 17 00:00:00 2001 From: Luke Shumaker Date: Wed, 5 Apr 2023 15:26:48 -0600 Subject: btrfsutil: RebuiltForrest.RebuiltTree(): Return errors --- lib/btrfsutil/rebuilt_forrest.go | 96 ++++++++++++++++++++++------------------ 1 file changed, 54 insertions(+), 42 deletions(-) (limited to 'lib/btrfsutil/rebuilt_forrest.go') diff --git a/lib/btrfsutil/rebuilt_forrest.go b/lib/btrfsutil/rebuilt_forrest.go index 4249396..a4ae727 100644 --- a/lib/btrfsutil/rebuilt_forrest.go +++ b/lib/btrfsutil/rebuilt_forrest.go @@ -6,6 +6,7 @@ package btrfsutil import ( "context" + "fmt" "github.com/datawire/dlib/dlog" @@ -13,6 +14,7 @@ import ( "git.lukeshu.com/btrfs-progs-ng/lib/btrfs/btrfsprim" "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" "git.lukeshu.com/btrfs-progs-ng/lib/slices" ) @@ -98,42 +100,57 @@ func NewRebuiltForrest(fs btrfs.ReadableFS, graph Graph, cb RebuiltForrestCallba } // RebuiltTree 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. // // This is identical to .ForrestLookup(), but returns a concrete type // rather than an interface. -func (ts *RebuiltForrest) RebuiltTree(ctx context.Context, treeID btrfsprim.ObjID) *RebuiltTree { +func (ts *RebuiltForrest) RebuiltTree(ctx context.Context, treeID btrfsprim.ObjID) (*RebuiltTree, error) { ctx = ts.treesMu.Lock(ctx) defer ts.treesMu.Unlock() - if !ts.addTree(ctx, treeID, nil) { - return nil + ts.rebuildTree(ctx, treeID, nil) + tree := ts.trees[treeID] + if tree.ancestorLoop && tree.rootErr == nil { + var loop []btrfsprim.ObjID + for ancestor := tree; true; ancestor = ancestor.Parent { + loop = append(loop, ancestor.ID) + if slices.Contains(ancestor.ID, loop[:len(loop)-1]) { + break + } + } + tree.rootErr = fmt.Errorf("loop detected: %v", loop) } - return ts.trees[treeID] + if tree.rootErr != nil { + return nil, tree.rootErr + } + return tree, nil } -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 +func (ts *RebuiltForrest) rebuildTree(ctx context.Context, treeID btrfsprim.ObjID, stack []btrfsprim.ObjID) { + loop := false + if maps.HasKey(ts.trees, treeID) { + loop = slices.Contains(treeID, stack) + if !loop { + return + } } + + stack = append(stack, treeID) + ctx = dlog.WithField(ctx, "btrfs.util.rebuilt-forrest.add-tree", stack) defer func() { - if !ok { - // Store a negative cache of this. tree.RebuiltAddRoot() for the ROOT or - // UUID trees will call .flushNegativeCache(). - ts.trees[treeID] = nil + if ts.trees[treeID].rootErr != nil { + dlog.Errorf(ctx, "failed to add tree: %v", ts.trees[treeID].rootErr) } }() - stack = append(stack, treeID) - 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) - return false + + if loop { + ts.trees[treeID].ancestorLoop = true + dlog.Error(ctx, "loop detected") + return } - tree := &RebuiltTree{ + ts.trees[treeID] = &RebuiltTree{ ID: treeID, Roots: make(containers.Set[btrfsvol.LogicalAddr]), forrest: ts, @@ -153,48 +170,43 @@ func (ts *RebuiltForrest) addTree(ctx context.Context, treeID btrfsprim.ObjID, s sb, _ := ts.inner.Superblock() root = 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 + ts.trees[treeID].rootErr = fmt.Errorf("failed to look up ROOT_ITEM") + return } root = rootItem.ByteNr - tree.UUID = rootItem.UUID + ts.trees[treeID].UUID = rootItem.UUID if rootItem.ParentUUID != (btrfsprim.UUID{}) { - tree.ParentGen = rootOff - if !ts.addTree(ctx, btrfsprim.UUID_TREE_OBJECTID, stack) { - return false - } + ts.trees[treeID].ParentGen = rootOff parentID, ok := ts.cb.LookupUUID(ctx, rootItem.ParentUUID) if !ok { - dlog.Errorf(ctx, "failed to add tree: lookup UUID %v", rootItem.ParentUUID) - return false + ts.trees[treeID].rootErr = fmt.Errorf("failed to look up UUID: %v", rootItem.ParentUUID) + return } - if !ts.addTree(ctx, parentID, stack) { - dlog.Errorf(ctx, "failed to add tree: add parent tree %v", parentID) - return false + ts.rebuildTree(ctx, parentID, stack) + ts.trees[treeID].Parent = ts.trees[parentID] + switch { + case ts.trees[treeID].Parent.ancestorLoop: + ts.trees[treeID].ancestorLoop = true + return + case ts.trees[treeID].Parent.rootErr != nil: + ts.trees[treeID].rootErr = fmt.Errorf("failed to rebuild parent tree: %v: %w", parentID, ts.trees[treeID].Parent.rootErr) + return } - tree.Parent = ts.trees[parentID] } } - ts.trees[treeID] = tree if root != 0 { - tree.RebuiltAddRoot(ctx, root) + ts.trees[treeID].RebuiltAddRoot(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 { + if tree.rootErr != nil || tree.ancestorLoop { delete(ts.trees, treeID) } } @@ -210,7 +222,7 @@ func (ts *RebuiltForrest) RebuiltListRoots(ctx context.Context) map[btrfsprim.Ob defer ts.treesMu.Unlock() ret := make(map[btrfsprim.ObjID]containers.Set[btrfsvol.LogicalAddr]) for treeID, tree := range ts.trees { - if tree != nil && len(tree.Roots) > 0 { + if len(tree.Roots) > 0 { ret[treeID] = tree.Roots } } -- cgit v1.2.3-54-g00ecf From ca4a23bc3c088b6a0222f7bf2c2bae5a3d7f9959 Mon Sep 17 00:00:00 2001 From: Luke Shumaker Date: Sat, 4 Mar 2023 09:42:44 -0700 Subject: btrfsutil: RebuiltForrest: Naively implement the new btrfs.ReadableFS API --- lib/btrfsutil/rebuilt_forrest.go | 40 +++++- lib/btrfsutil/rebuilt_forrest_test.go | 2 +- lib/btrfsutil/rebuilt_tree.go | 260 ++++++++++++++++++++++++++++++++++ 3 files changed, 300 insertions(+), 2 deletions(-) (limited to 'lib/btrfsutil/rebuilt_forrest.go') diff --git a/lib/btrfsutil/rebuilt_forrest.go b/lib/btrfsutil/rebuilt_forrest.go index a4ae727..b935d85 100644 --- a/lib/btrfsutil/rebuilt_forrest.go +++ b/lib/btrfsutil/rebuilt_forrest.go @@ -12,6 +12,7 @@ import ( "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/containers" "git.lukeshu.com/btrfs-progs-ng/lib/maps" @@ -172,7 +173,7 @@ func (ts *RebuiltForrest) rebuildTree(ctx context.Context, treeID btrfsprim.ObjI default: rootOff, rootItem, ok := ts.cb.LookupRoot(ctx, treeID) if !ok { - ts.trees[treeID].rootErr = fmt.Errorf("failed to look up ROOT_ITEM") + ts.trees[treeID].rootErr = btrfstree.ErrNoTree return } root = rootItem.ByteNr @@ -228,3 +229,40 @@ func (ts *RebuiltForrest) RebuiltListRoots(ctx context.Context) map[btrfsprim.Ob } return ret } + +// btrfs.ReadableFS interface ////////////////////////////////////////////////////////////////////////////////////////// + +var _ btrfs.ReadableFS = (*RebuiltForrest)(nil) + +// Name implements btrfs.ReadableFS. +func (ts *RebuiltForrest) Name() string { + return ts.inner.Name() +} + +// ForrestLookup implements btrfstree.Forrest (and btrfs.ReadableFS). +// +// It is identical to .RebuiltTree(), but returns an interface rather +// than a concrete type. +func (ts *RebuiltForrest) ForrestLookup(ctx context.Context, treeID btrfsprim.ObjID) (btrfstree.Tree, error) { + return ts.RebuiltTree(ctx, treeID) +} + +// Superblock implements btrfstree.NodeSource (and btrfs.ReadableFS). +func (ts *RebuiltForrest) Superblock() (*btrfstree.Superblock, error) { + return ts.inner.Superblock() +} + +// AcquireNode implements btrfstree.NodeSource (and btrfs.ReadableFS). +func (ts *RebuiltForrest) AcquireNode(ctx context.Context, addr btrfsvol.LogicalAddr, exp btrfstree.NodeExpectations) (*btrfstree.Node, error) { + return ts.inner.AcquireNode(ctx, addr, exp) +} + +// ReleaseNode implements btrfstree.NodeSource (and btrfs.ReadableFS). +func (ts *RebuiltForrest) ReleaseNode(node *btrfstree.Node) { + ts.inner.ReleaseNode(node) +} + +// ReadAt implements diskio.ReaderAt[btrfsvol.LogicalAddr] (and btrfs.ReadableFS). +func (ts *RebuiltForrest) ReadAt(p []byte, off btrfsvol.LogicalAddr) (int, error) { + return ts.inner.ReadAt(p, off) +} diff --git a/lib/btrfsutil/rebuilt_forrest_test.go b/lib/btrfsutil/rebuilt_forrest_test.go index 6f80eff..96749c4 100644 --- a/lib/btrfsutil/rebuilt_forrest_test.go +++ b/lib/btrfsutil/rebuilt_forrest_test.go @@ -188,6 +188,6 @@ func TestRebuiltTreeParentErr(t *testing.T) { rfs := NewRebuiltForrest(nil, Graph{}, cbs) tree, err := rfs.RebuiltTree(ctx, 305) - assert.EqualError(t, err, `failed to rebuild parent tree: 304: failed to look up ROOT_ITEM`) + assert.EqualError(t, err, `failed to rebuild parent tree: 304: tree does not exist`) assert.Nil(t, tree) } diff --git a/lib/btrfsutil/rebuilt_tree.go b/lib/btrfsutil/rebuilt_tree.go index 5d38bb1..9ab0356 100644 --- a/lib/btrfsutil/rebuilt_tree.go +++ b/lib/btrfsutil/rebuilt_tree.go @@ -14,6 +14,7 @@ import ( "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/containers" "git.lukeshu.com/btrfs-progs-ng/lib/maps" @@ -510,3 +511,262 @@ func (tree *RebuiltTree) RebuiltLeafToRoots(ctx context.Context, leaf btrfsvol.L } return ret } + +// btrfstree.Tree interface //////////////////////////////////////////////////////////////////////////////////////////// + +var _ btrfstree.Tree = (*RebuiltTree)(nil) + +// TreeParentID implements btrfstree.Tree. +func (tree *RebuiltTree) TreeParentID(_ context.Context) (btrfsprim.ObjID, btrfsprim.Generation, error) { + if tree.Parent == nil { + return 0, 0, nil + } + return tree.Parent.ID, tree.ParentGen, nil +} + +// TreeLookup implements btrfstree.Tree. +// +// BUG(lukeshu): Errors in the tree are not ever returned. +func (tree *RebuiltTree) TreeLookup(ctx context.Context, key btrfsprim.Key) (btrfstree.Item, error) { + return tree.TreeSearch(ctx, btrfstree.SearchExactKey(key)) +} + +// TreeSearch implements btrfstree.Tree. It is a thin wrapper around +// tree.RebuiltItems(ctx).Search (to do the search) and +// tree.TreeLookup (to read item bodies). +// +// BUG(lukeshu): Errors in the tree are not ever returned. +func (tree *RebuiltTree) TreeSearch(ctx context.Context, searcher btrfstree.TreeSearcher) (btrfstree.Item, error) { + _, ptr, ok := tree.RebuiltAcquireItems(ctx).Search(func(_ btrfsprim.Key, ptr ItemPtr) int { + straw := tree.forrest.graph.Nodes[ptr.Node].Items[ptr.Slot] + return searcher.Search(straw.Key, straw.Size) + }) + tree.RebuiltReleaseItems() + if !ok { + return btrfstree.Item{}, fmt.Errorf("item with %s: %w", searcher, btrfstree.ErrNoItem) + } + return tree.forrest.readItem(ctx, ptr), nil +} + +// TreeRange implements btrfstree.Tree. It is a thin wrapper around +// tree.RebuiltItems(ctx).Range (to do the iteration) and +// tree.TreeLookup (to read item bodies). +// +// BUG(lukeshu): Errors in the tree are not ever returned. +func (tree *RebuiltTree) TreeRange(ctx context.Context, handleFn func(btrfstree.Item) bool) error { + tree.RebuiltAcquireItems(ctx).Range(func(_ btrfsprim.Key, ptr ItemPtr) bool { + return handleFn(tree.forrest.readItem(ctx, ptr)) + }) + tree.RebuiltReleaseItems() + return nil +} + +// TreeSubrange implements btrfstree.Tree. It is a thin wrapper +// around tree.RebuiltItems(ctx).Subrange (to do the iteration) and +// tree.TreeLookup (to read item bodies). +// +// BUG(lukeshu): Errors in the tree are not ever returned. +func (tree *RebuiltTree) TreeSubrange(ctx context.Context, + min int, + searcher btrfstree.TreeSearcher, + handleFn func(btrfstree.Item) bool, +) error { + var cnt int + tree.RebuiltAcquireItems(ctx).Subrange( + func(_ btrfsprim.Key, ptr ItemPtr) int { + straw := tree.forrest.graph.Nodes[ptr.Node].Items[ptr.Slot] + return searcher.Search(straw.Key, straw.Size) + }, + func(_ btrfsprim.Key, ptr ItemPtr) bool { + cnt++ + return handleFn(tree.forrest.readItem(ctx, ptr)) + }, + ) + tree.RebuiltReleaseItems() + + if cnt < min { + return btrfstree.ErrNoItem + } + + return nil +} + +// TreeWalk implements btrfstree.Tree. +func (tree *RebuiltTree) TreeWalk(ctx context.Context, cbs btrfstree.TreeWalkHandler) { + tree.mu.RLock() + defer tree.mu.RUnlock() + + if _, err := tree.forrest.Superblock(); err != nil && cbs.BadSuperblock != nil { + cbs.BadSuperblock(err) + } + + walker := &rebuiltWalker{ + // Input: tree + tree: tree, + nodeIndex: tree.acquireNodeIndex(ctx), + items: tree.RebuiltAcquireItems(ctx), + + // Input: args + cbs: cbs, + + // State + visited: make(containers.Set[btrfsvol.LogicalAddr]), + } + defer tree.releaseNodeIndex() + defer tree.RebuiltReleaseItems() + + for _, root := range maps.SortedKeys(tree.Roots) { + path := btrfstree.Path{ + btrfstree.PathRoot{ + Forrest: tree.forrest, + TreeID: tree.ID, + ToAddr: root, + ToGeneration: tree.forrest.graph.Nodes[root].Generation, + ToLevel: tree.forrest.graph.Nodes[root].Level, + }, + } + walker.walk(ctx, path) + if ctx.Err() != nil { + return + } + } +} + +type rebuiltWalker struct { + // Input: tree + tree *RebuiltTree + nodeIndex rebuiltNodeIndex + items *containers.SortedMap[btrfsprim.Key, ItemPtr] + + // Input: args + cbs btrfstree.TreeWalkHandler + + // State + visited containers.Set[btrfsvol.LogicalAddr] +} + +func (walker *rebuiltWalker) walk(ctx context.Context, path btrfstree.Path) { + if ctx.Err() != nil { + return + } + + // 001 + nodeAddr, nodeExp, ok := path.NodeExpectations(ctx, true) + if !ok { + panic(fmt.Errorf("should not happen: btrfsutil.rebuiltWalker.walk called with non-node path: %v", + path)) + } + if err := walker.tree.forrest.graph.BadNodes[nodeAddr]; err != nil { + if walker.cbs.BadNode != nil { + _ = walker.cbs.BadNode(path, nil, err) + } + return + } + // 001-002 + nodeInfo := walker.tree.forrest.graph.Nodes[nodeAddr] + if err := nodeInfo.CheckExpectations(walker.tree.forrest.graph, nodeExp); err != nil { + if walker.cbs.BadNode != nil { + // 001 + node, _ := walker.tree.forrest.AcquireNode(ctx, nodeAddr, nodeExp) + defer walker.tree.forrest.ReleaseNode(node) + if ctx.Err() != nil { + return + } + // 002 + _ = walker.cbs.BadNode(path, node, err) + } + return + } + if walker.visited.Has(nodeAddr) { + return + } + walker.visited.Insert(nodeAddr) + if walker.cbs.Node != nil { + // 001 + node, _ := walker.tree.forrest.AcquireNode(ctx, nodeAddr, nodeExp) + if ctx.Err() != nil { + walker.tree.forrest.ReleaseNode(node) + return + } + // 002 + walker.cbs.Node(path, node) + walker.tree.forrest.ReleaseNode(node) + if ctx.Err() != nil { + return + } + } + + // branch a (interior) + for i, kp := range walker.tree.forrest.graph.EdgesFrom[nodeAddr] { + var toMaxKey btrfsprim.Key + for root, rootInfo := range walker.nodeIndex.nodeToRoots[nodeAddr] { + if !walker.tree.Roots.Has(root) { + continue + } + if rootInfo.hiMaxItem.Compare(toMaxKey) > 0 { + toMaxKey = rootInfo.hiMaxItem + } + } + itemPath := append(path, btrfstree.PathKP{ + FromTree: walker.tree.forrest.graph.Nodes[nodeAddr].Owner, + FromSlot: i, + + ToAddr: kp.ToNode, + ToGeneration: kp.ToGeneration, + ToMinKey: kp.ToKey, + + ToMaxKey: toMaxKey, + ToLevel: kp.ToLevel, + }) + // 003a + recurse := walker.cbs.KeyPointer == nil || walker.cbs.KeyPointer(itemPath, btrfstree.KeyPointer{ + Key: kp.ToKey, + BlockPtr: kp.ToNode, + Generation: kp.ToGeneration, + }) + if ctx.Err() != nil { + return + } + // 004a + if recurse { + walker.walk(ctx, itemPath) + if ctx.Err() != nil { + return + } + } + } + + // branch b (leaf) + if walker.cbs.Item != nil || walker.cbs.BadItem != nil { + for i, keyAndSize := range walker.tree.forrest.graph.Nodes[nodeAddr].Items { + ptr, ok := walker.items.Load(keyAndSize.Key) + if !ok { + panic(fmt.Errorf("should not happen: index does not contain present item %v", keyAndSize.Key)) + } + if ptr.Node != nodeAddr { + continue + } + itemPath := append(path, btrfstree.PathItem{ + FromTree: walker.tree.forrest.graph.Nodes[nodeAddr].Owner, + FromSlot: i, + + ToKey: keyAndSize.Key, + }) + item := walker.tree.forrest.readItem(ctx, ptr) + // 003b + switch item.Body.(type) { + case *btrfsitem.Error: + if walker.cbs.BadItem != nil { + walker.cbs.BadItem(itemPath, item) + } + default: + if walker.cbs.Item != nil { + walker.cbs.Item(itemPath, item) + } + } + if ctx.Err() != nil { + return + } + } + } +} -- cgit v1.2.3-54-g00ecf