From 2c157587cd6b7cb03d169327f397cd4c01b872f9 Mon Sep 17 00:00:00 2001 From: Luke Shumaker Date: Sat, 4 Mar 2023 09:42:44 -0700 Subject: btrfsutil: Graph: Track item sizes --- lib/btrfsutil/graph.go | 19 +++++++++++++------ lib/btrfsutil/rebuilt_tree.go | 12 ++++++------ 2 files changed, 19 insertions(+), 12 deletions(-) diff --git a/lib/btrfsutil/graph.go b/lib/btrfsutil/graph.go index 860a49c..1b55642 100644 --- a/lib/btrfsutil/graph.go +++ b/lib/btrfsutil/graph.go @@ -24,12 +24,17 @@ import ( "git.lukeshu.com/btrfs-progs-ng/lib/textui" ) +type KeyAndSize struct { + Key btrfsprim.Key + Size uint32 +} + type GraphNode struct { Addr btrfsvol.LogicalAddr Level uint8 Generation btrfsprim.Generation Owner btrfsprim.ObjID - Items []btrfsprim.Key + Items []KeyAndSize } func (n GraphNode) NumItems(g Graph) int { @@ -47,7 +52,7 @@ func (n GraphNode) MinItem(g Graph) btrfsprim.Key { } switch n.Level { case 0: - return n.Items[0] + return n.Items[0].Key default: return g.EdgesFrom[n.Addr][0].ToKey } @@ -59,7 +64,7 @@ func (n GraphNode) MaxItem(g Graph) btrfsprim.Key { } switch n.Level { case 0: - return n.Items[len(n.Items)-1] + return n.Items[len(n.Items)-1].Key default: return g.EdgesFrom[n.Addr][len(g.EdgesFrom[n.Addr])-1].ToKey } @@ -225,11 +230,13 @@ func (g Graph) InsertNode(node *btrfstree.Node) { } } kps := make([]GraphEdge, 0, cnt) - keys := make([]btrfsprim.Key, len(node.BodyLeaf)) - nodeData.Items = keys + nodeData.Items = make([]KeyAndSize, len(node.BodyLeaf)) g.Nodes[node.Head.Addr] = nodeData for i, item := range node.BodyLeaf { - keys[i] = item.Key + nodeData.Items[i] = KeyAndSize{ + Key: item.Key, + Size: item.BodySize, + } if itemBody, ok := item.Body.(*btrfsitem.Root); ok { kps = append(kps, GraphEdge{ FromRoot: node.Head.Addr, diff --git a/lib/btrfsutil/rebuilt_tree.go b/lib/btrfsutil/rebuilt_tree.go index 177b859..12d5978 100644 --- a/lib/btrfsutil/rebuilt_tree.go +++ b/lib/btrfsutil/rebuilt_tree.go @@ -329,17 +329,17 @@ func (tree *RebuiltTree) items(ctx context.Context, inc bool) containers.SortedM for i, leaf := range leafs { stats.Leafs.N = i progressWriter.Set(stats) - for j, itemKey := range tree.forrest.graph.Nodes[leaf].Items { + for j, itemKeyAndSize := range tree.forrest.graph.Nodes[leaf].Items { newPtr := ItemPtr{ Node: leaf, Slot: j, } - if oldPtr, exists := index.Load(itemKey); !exists { - index.Store(itemKey, newPtr) + if oldPtr, exists := index.Load(itemKeyAndSize.Key); !exists { + index.Store(itemKeyAndSize.Key, newPtr) stats.NumItems++ } else { if tree.RebuiltShouldReplace(oldPtr.Node, newPtr.Node) { - index.Store(itemKey, newPtr) + index.Store(itemKeyAndSize.Key, newPtr) } stats.NumDups++ } @@ -425,8 +425,8 @@ func (tree *RebuiltTree) RebuiltAddRoot(ctx context.Context, rootNode btrfsvol.L stats.AddedLeafs++ progressWriter.Set(stats) - for _, itemKey := range tree.forrest.graph.Nodes[leaf].Items { - extCB.AddedItem(ctx, tree.ID, itemKey) + for _, itemKeyAndSize := range tree.forrest.graph.Nodes[leaf].Items { + extCB.AddedItem(ctx, tree.ID, itemKeyAndSize.Key) stats.AddedItems++ progressWriter.Set(stats) } -- cgit v1.1-4-g5e80 From df6444f337ae24220b4e14443d9cd6e74e8d0606 Mon Sep 17 00:00:00 2001 From: Luke Shumaker Date: Fri, 31 Mar 2023 12:26:58 -0600 Subject: btrfsutil: RebuiltTree: Track member interior nodes too --- lib/btrfsutil/rebuilt_tree.go | 38 +++++++++++++++++++------------------- 1 file changed, 19 insertions(+), 19 deletions(-) diff --git a/lib/btrfsutil/rebuilt_tree.go b/lib/btrfsutil/rebuilt_tree.go index 12d5978..c291319 100644 --- a/lib/btrfsutil/rebuilt_tree.go +++ b/lib/btrfsutil/rebuilt_tree.go @@ -81,9 +81,9 @@ type rebuiltPathInfo struct { } type rebuiltNodeIndex struct { - // leafToRoots contains all leafs (lvl=0) in the filesystem - // that pass .isOwnerOK, whether or not they're in the tree. - leafToRoots map[btrfsvol.LogicalAddr]rebuiltRoots + // nodeToRoots contains all nodes in the filesystem that pass + // .isOwnerOK, whether or not they're in the tree. + nodeToRoots map[btrfsvol.LogicalAddr]rebuiltRoots } func (tree *RebuiltTree) acquireNodeIndex(ctx context.Context) rebuiltNodeIndex { @@ -108,11 +108,11 @@ func (tree *RebuiltTree) uncachedNodeIndex(ctx context.Context) rebuiltNodeIndex } ret := rebuiltNodeIndex{ - leafToRoots: make(map[btrfsvol.LogicalAddr]rebuiltRoots), + nodeToRoots: make(map[btrfsvol.LogicalAddr]rebuiltRoots), } for node, roots := range indexer.run(ctx) { - if tree.forrest.graph.Nodes[node].Level == 0 && len(roots) > 0 { - ret.leafToRoots[node] = roots + if len(roots) > 0 { + ret.nodeToRoots[node] = roots } } return ret @@ -313,9 +313,9 @@ func (tree *RebuiltTree) items(ctx context.Context, inc bool) containers.SortedM defer tree.mu.RUnlock() var leafs []btrfsvol.LogicalAddr - for leaf, roots := range tree.acquireNodeIndex(ctx).leafToRoots { - if maps.HaveAnyKeysInCommon(tree.Roots, roots) == inc { - leafs = append(leafs, leaf) + for node, roots := range tree.acquireNodeIndex(ctx).nodeToRoots { + if tree.forrest.graph.Nodes[node].Level == 0 && maps.HaveAnyKeysInCommon(tree.Roots, roots) == inc { + leafs = append(leafs, node) } } tree.releaseNodeIndex() @@ -388,14 +388,14 @@ func (tree *RebuiltTree) RebuiltShouldReplace(oldNode, newNode btrfsvol.LogicalA } type rebuiltRootStats struct { - Leafs textui.Portion[int] + Nodes textui.Portion[int] AddedLeafs int AddedItems int } func (s rebuiltRootStats) String() string { return textui.Sprintf("%v (added %v leafs, added %v items)", - s.Leafs, s.AddedLeafs, s.AddedItems) + s.Nodes, s.AddedLeafs, s.AddedItems) } // RebuiltAddRoot adds an additional root node to the tree. It is @@ -411,27 +411,27 @@ func (tree *RebuiltTree) RebuiltAddRoot(ctx context.Context, rootNode btrfsvol.L if extCB, ok := tree.forrest.cb.(RebuiltForrestExtendedCallbacks); ok { var stats rebuiltRootStats - leafToRoots := tree.acquireNodeIndex(ctx).leafToRoots - stats.Leafs.D = len(leafToRoots) + nodeToRoots := tree.acquireNodeIndex(ctx).nodeToRoots + stats.Nodes.D = len(nodeToRoots) progressWriter := textui.NewProgress[rebuiltRootStats](ctx, dlog.LogLevelInfo, textui.Tunable(1*time.Second)) - for i, leaf := range maps.SortedKeys(leafToRoots) { - stats.Leafs.N = i + for i, node := range maps.SortedKeys(nodeToRoots) { + stats.Nodes.N = i progressWriter.Set(stats) - if maps.HaveAnyKeysInCommon(tree.Roots, leafToRoots[leaf]) || !maps.HasKey(leafToRoots[leaf], rootNode) { + if tree.forrest.graph.Nodes[node].Level > 0 || maps.HaveAnyKeysInCommon(tree.Roots, nodeToRoots[node]) || !maps.HasKey(nodeToRoots[node], rootNode) { continue } stats.AddedLeafs++ progressWriter.Set(stats) - for _, itemKeyAndSize := range tree.forrest.graph.Nodes[leaf].Items { + for _, itemKeyAndSize := range tree.forrest.graph.Nodes[node].Items { extCB.AddedItem(ctx, tree.ID, itemKeyAndSize.Key) stats.AddedItems++ progressWriter.Set(stats) } } - stats.Leafs.N = len(leafToRoots) + stats.Nodes.N = len(nodeToRoots) tree.releaseNodeIndex() progressWriter.Set(stats) progressWriter.Done() @@ -486,7 +486,7 @@ func (tree *RebuiltTree) RebuiltLeafToRoots(ctx context.Context, leaf btrfsvol.L tree.mu.RLock() defer tree.mu.RUnlock() ret := make(containers.Set[btrfsvol.LogicalAddr]) - for root := range tree.acquireNodeIndex(ctx).leafToRoots[leaf] { + for root := range tree.acquireNodeIndex(ctx).nodeToRoots[leaf] { if tree.Roots.Has(root) { panic(fmt.Errorf("should not happen: (tree=%v).RebuiltLeafToRoots(leaf=%v): tree contains root=%v but not leaf", tree.ID, leaf, root)) -- cgit v1.1-4-g5e80 From c9ca78f970f0b48fbf6965e8ec15f6b8f31ce485 Mon Sep 17 00:00:00 2001 From: Luke Shumaker Date: Wed, 5 Apr 2023 11:23:03 -0600 Subject: btrfsutil: RebuiltForrest: readItem: Return a full btrfstree.Item --- lib/btrfsutil/rebuilt_callbacks.go | 12 ++++++------ lib/btrfsutil/rebuilt_readitem.go | 8 +++++--- lib/btrfsutil/rebuilt_tree.go | 2 +- 3 files changed, 12 insertions(+), 10 deletions(-) diff --git a/lib/btrfsutil/rebuilt_callbacks.go b/lib/btrfsutil/rebuilt_callbacks.go index 3a7e6e6..41fe7f1 100644 --- a/lib/btrfsutil/rebuilt_callbacks.go +++ b/lib/btrfsutil/rebuilt_callbacks.go @@ -48,9 +48,9 @@ func (cb noopRebuiltForrestCallbacks) LookupRoot(ctx context.Context, tree btrfs if !ok { return 0, btrfsitem.Root{}, false } - itemBody := cb.forrest.readItem(ctx, itemPtr) - defer itemBody.Free() - switch itemBody := itemBody.(type) { + item := cb.forrest.readItem(ctx, itemPtr) + defer item.Body.Free() + switch itemBody := item.Body.(type) { case *btrfsitem.Root: return btrfsprim.Generation(itemKey.Offset), *itemBody, true case *btrfsitem.Error: @@ -73,9 +73,9 @@ func (cb noopRebuiltForrestCallbacks) LookupUUID(ctx context.Context, uuid btrfs if !ok { return 0, false } - itemBody := cb.forrest.readItem(ctx, itemPtr) - defer itemBody.Free() - switch itemBody := itemBody.(type) { + item := cb.forrest.readItem(ctx, itemPtr) + defer item.Body.Free() + switch itemBody := item.Body.(type) { case *btrfsitem.UUIDMap: return itemBody.ObjID, true case *btrfsitem.Error: diff --git a/lib/btrfsutil/rebuilt_readitem.go b/lib/btrfsutil/rebuilt_readitem.go index d1d1319..e5faa45 100644 --- a/lib/btrfsutil/rebuilt_readitem.go +++ b/lib/btrfsutil/rebuilt_readitem.go @@ -8,7 +8,6 @@ import ( "context" "fmt" - "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" @@ -24,7 +23,7 @@ func (ptr ItemPtr) String() string { return fmt.Sprintf("node@%v[%v]", ptr.Node, ptr.Slot) } -func (ts *RebuiltForrest) readItem(ctx context.Context, ptr ItemPtr) btrfsitem.Item { +func (ts *RebuiltForrest) readItem(ctx context.Context, ptr ItemPtr) btrfstree.Item { graphInfo, ok := ts.graph.Nodes[ptr.Node] if !ok { panic(fmt.Errorf("should not happen: btrfsutil.RebuiltForrest.readItem called for node@%v not mentioned in the in-memory graph", ptr.Node)) @@ -62,5 +61,8 @@ func (ts *RebuiltForrest) readItem(ctx context.Context, ptr ItemPtr) btrfsitem.I panic(fmt.Errorf("should not happen: btrfsutil.RebuiltForrest.readItem called for out-of-bounds item slot: slot=%v len=%v", ptr.Slot, len(items))) } - return items[ptr.Slot].Body.CloneItem() + + item := items[ptr.Slot] + item.Body = item.Body.CloneItem() + return item } diff --git a/lib/btrfsutil/rebuilt_tree.go b/lib/btrfsutil/rebuilt_tree.go index c291319..ca5ccf3 100644 --- a/lib/btrfsutil/rebuilt_tree.go +++ b/lib/btrfsutil/rebuilt_tree.go @@ -473,7 +473,7 @@ func (tree *RebuiltTree) ReadItem(ctx context.Context, key btrfsprim.Key) btrfsi if !ok { panic(fmt.Errorf("should not happen: btrfsutil.RebuiltTree.ReadItem called for not-included key: %v", key)) } - return tree.forrest.readItem(ctx, ptr) + return tree.forrest.readItem(ctx, ptr).Body } // RebuiltLeafToRoots returns the list of potential roots (to pass to -- cgit v1.1-4-g5e80 From 2bca1422067e0de0a5ec1b37c37f280e797a8072 Mon Sep 17 00:00:00 2001 From: Luke Shumaker Date: Sat, 8 Apr 2023 18:34:00 -0600 Subject: btrfsutil: RebuiltForrest: Have the ancestor id-to-ptr map persist --- lib/btrfsutil/rebuilt_tree.go | 4 ++++ 1 file changed, 4 insertions(+) diff --git a/lib/btrfsutil/rebuilt_tree.go b/lib/btrfsutil/rebuilt_tree.go index ca5ccf3..e507851 100644 --- a/lib/btrfsutil/rebuilt_tree.go +++ b/lib/btrfsutil/rebuilt_tree.go @@ -81,6 +81,9 @@ type rebuiltPathInfo struct { } type rebuiltNodeIndex struct { + // idToTree contains this tree, and all of its ancestor trees. + idToTree map[btrfsprim.ObjID]*RebuiltTree + // nodeToRoots contains all nodes in the filesystem that pass // .isOwnerOK, whether or not they're in the tree. nodeToRoots map[btrfsvol.LogicalAddr]rebuiltRoots @@ -108,6 +111,7 @@ func (tree *RebuiltTree) uncachedNodeIndex(ctx context.Context) rebuiltNodeIndex } ret := rebuiltNodeIndex{ + idToTree: indexer.idToTree, nodeToRoots: make(map[btrfsvol.LogicalAddr]rebuiltRoots), } for node, roots := range indexer.run(ctx) { -- cgit v1.1-4-g5e80 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 --- cmd/btrfs-rec/inspect/rebuildtrees/rebuild.go | 15 +- .../inspect/rebuildtrees/rebuild_treecb.go | 4 +- .../inspect/rebuildtrees/rebuild_wantcb.go | 18 +- cmd/btrfs-rec/inspect/rebuildtrees/util.go | 4 + lib/btrfsutil/rebuilt_callbacks.go | 8 +- lib/btrfsutil/rebuilt_forrest.go | 96 +++++----- lib/btrfsutil/rebuilt_forrest_test.go | 193 +++++++++++++++++++++ lib/btrfsutil/rebuilt_tree.go | 9 +- 8 files changed, 281 insertions(+), 66 deletions(-) create mode 100644 lib/btrfsutil/rebuilt_forrest_test.go diff --git a/cmd/btrfs-rec/inspect/rebuildtrees/rebuild.go b/cmd/btrfs-rec/inspect/rebuildtrees/rebuild.go index d1ccfac..7e2e49f 100644 --- a/cmd/btrfs-rec/inspect/rebuildtrees/rebuild.go +++ b/cmd/btrfs-rec/inspect/rebuildtrees/rebuild.go @@ -159,7 +159,7 @@ func (o *rebuilder) processTreeQueue(ctx context.Context) error { } // This will call o.AddedItem as nescessary, which // inserts to o.addedItemQueue. - _ = o.rebuilt.RebuiltTree(ctx, o.curKey.TreeID) + _, _ = o.rebuilt.RebuiltTree(ctx, o.curKey.TreeID) } return nil @@ -197,7 +197,7 @@ func (o *rebuilder) processAddedItemQueue(ctx context.Context) error { for _, key := range queue { ctx := dlog.WithField(ctx, "btrfs.inspect.rebuild-trees.rebuild.settle.item", key) - tree := o.rebuilt.RebuiltTree(ctx, key.TreeID) + tree := discardErr(o.rebuilt.RebuiltTree(ctx, key.TreeID)) incPtr, ok := tree.RebuiltAcquireItems(ctx).Load(key.Key) tree.RebuiltReleaseItems() if !ok { @@ -333,9 +333,8 @@ func (o *rebuilder) sortSettledItemQueue(ctx context.Context, unorderedQueue con // EXTENT_TREE; if that fails, then there can't be any items // in the EXTENT_TREE for us to have to handle special, and // all of the following code will fall through common-path. - extentTree := o.rebuilt.RebuiltTree(ctx, btrfsprim.EXTENT_TREE_OBJECTID) var extentItems *containers.SortedMap[btrfsprim.Key, btrfsutil.ItemPtr] - if extentTree != nil { + if extentTree, err := o.rebuilt.RebuiltTree(ctx, btrfsprim.EXTENT_TREE_OBJECTID); err == nil { extentItems = extentTree.RebuiltAcquireItems(ctx) defer extentTree.RebuiltReleaseItems() } @@ -416,7 +415,7 @@ func (o *rebuilder) processSettledItemQueue(ctx context.Context) error { ctx := dlog.WithField(ctx, "btrfs.inspect.rebuild-trees.rebuild.process.item", key) item := keyAndBody{ itemToVisit: key, - Body: o.rebuilt.RebuiltTree(ctx, key.TreeID).ReadItem(ctx, key.Key), + Body: discardErr(o.rebuilt.RebuiltTree(ctx, key.TreeID)).ReadItem(ctx, key.Key), } if key.TreeID == btrfsprim.EXTENT_TREE_OBJECTID && (key.ItemType == btrfsprim.EXTENT_ITEM_KEY || key.ItemType == btrfsprim.METADATA_ITEM_KEY) { @@ -503,7 +502,7 @@ func (o *rebuilder) processAugmentQueue(ctx context.Context) error { } // This will call o.AddedItem as nescessary, which // inserts to o.addedItemQueue. - o.rebuilt.RebuiltTree(ctx, treeID).RebuiltAddRoot(ctx, nodeAddr) + discardErr(o.rebuilt.RebuiltTree(ctx, treeID)).RebuiltAddRoot(ctx, nodeAddr) progress.N++ progressWriter.Set(progress) } @@ -550,7 +549,7 @@ func (o *rebuilder) resolveTreeAugments(ctx context.Context, treeID btrfsprim.Ob } else { choices[choice] = ChoiceInfo{ Count: 1, - Distance: discardOK(o.rebuilt.RebuiltTree(ctx, treeID).RebuiltCOWDistance(o.scan.Graph.Nodes[choice].Owner)), + Distance: discardOK(discardErr(o.rebuilt.RebuiltTree(ctx, treeID)).RebuiltCOWDistance(o.scan.Graph.Nodes[choice].Owner)), Generation: o.scan.Graph.Nodes[choice].Generation, } } @@ -564,7 +563,7 @@ func (o *rebuilder) resolveTreeAugments(ctx context.Context, treeID btrfsprim.Ob } else { choices[choice] = ChoiceInfo{ Count: 1, - Distance: discardOK(o.rebuilt.RebuiltTree(ctx, treeID).RebuiltCOWDistance(o.scan.Graph.Nodes[choice].Owner)), + Distance: discardOK(discardErr(o.rebuilt.RebuiltTree(ctx, treeID)).RebuiltCOWDistance(o.scan.Graph.Nodes[choice].Owner)), Generation: o.scan.Graph.Nodes[choice].Generation, } } diff --git a/cmd/btrfs-rec/inspect/rebuildtrees/rebuild_treecb.go b/cmd/btrfs-rec/inspect/rebuildtrees/rebuild_treecb.go index 0c52556..e227cc7 100644 --- a/cmd/btrfs-rec/inspect/rebuildtrees/rebuild_treecb.go +++ b/cmd/btrfs-rec/inspect/rebuildtrees/rebuild_treecb.go @@ -51,7 +51,7 @@ func (o forrestCallbacks) LookupRoot(ctx context.Context, tree btrfsprim.ObjID) o.enqueueRetry(btrfsprim.ROOT_TREE_OBJECTID) return 0, btrfsitem.Root{}, false } - itemBody := o.rebuilt.RebuiltTree(ctx, wantKey.TreeID).ReadItem(ctx, foundKey) + itemBody := discardErr(o.rebuilt.RebuiltTree(ctx, wantKey.TreeID)).ReadItem(ctx, foundKey) defer itemBody.Free() switch itemBody := itemBody.(type) { case *btrfsitem.Root: @@ -77,7 +77,7 @@ func (o forrestCallbacks) LookupUUID(ctx context.Context, uuid btrfsprim.UUID) ( o.enqueueRetry(btrfsprim.UUID_TREE_OBJECTID) return 0, false } - itemBody := o.rebuilt.RebuiltTree(ctx, wantKey.TreeID).ReadItem(ctx, wantKey.Key.Key()) + itemBody := discardErr(o.rebuilt.RebuiltTree(ctx, wantKey.TreeID)).ReadItem(ctx, wantKey.Key.Key()) defer itemBody.Free() switch itemBody := itemBody.(type) { case *btrfsitem.UUIDMap: diff --git a/cmd/btrfs-rec/inspect/rebuildtrees/rebuild_wantcb.go b/cmd/btrfs-rec/inspect/rebuildtrees/rebuild_wantcb.go index 0526e93..382d88b 100644 --- a/cmd/btrfs-rec/inspect/rebuildtrees/rebuild_wantcb.go +++ b/cmd/btrfs-rec/inspect/rebuildtrees/rebuild_wantcb.go @@ -43,8 +43,8 @@ func (o graphCallbacks) Want(ctx context.Context, reason string, treeID btrfspri } func (o *rebuilder) _want(ctx context.Context, wantKey wantWithTree) (key btrfsprim.Key, ok bool) { - tree := o.rebuilt.RebuiltTree(ctx, wantKey.TreeID) - if tree == nil { + tree, err := o.rebuilt.RebuiltTree(ctx, wantKey.TreeID) + if err != nil { o.enqueueRetry(wantKey.TreeID) return btrfsprim.Key{}, false } @@ -98,8 +98,8 @@ func (o graphCallbacks) WantOff(ctx context.Context, reason string, treeID btrfs } func (o *rebuilder) _wantOff(ctx context.Context, wantKey wantWithTree) (ok bool) { - tree := o.rebuilt.RebuiltTree(ctx, wantKey.TreeID) - if tree == nil { + tree, err := o.rebuilt.RebuiltTree(ctx, wantKey.TreeID) + if err != nil { o.enqueueRetry(wantKey.TreeID) return false } @@ -144,8 +144,8 @@ func (o graphCallbacks) WantDirIndex(ctx context.Context, reason string, treeID } ctx = withWant(ctx, logFieldItemWant, reason, wantKey) - tree := o.rebuilt.RebuiltTree(ctx, treeID) - if tree == nil { + tree, err := o.rebuilt.RebuiltTree(ctx, treeID) + if err != nil { o.enqueueRetry(treeID) return } @@ -273,8 +273,8 @@ func (o graphCallbacks) _wantRange( ctx = withWant(ctx, logFieldItemWant, reason, wantKey) wantKey.Key.OffsetType = offsetRange - tree := o.rebuilt.RebuiltTree(ctx, treeID) - if tree == nil { + tree, err := o.rebuilt.RebuiltTree(ctx, treeID) + if err != nil { o.enqueueRetry(treeID) return } @@ -389,7 +389,7 @@ func (o graphCallbacks) WantCSum(ctx context.Context, reason string, inodeTree, o.enqueueRetry(inodeTree) return } - tree := o.rebuilt.RebuiltTree(inodeCtx, inodeTree) + tree := discardErr(o.rebuilt.RebuiltTree(inodeCtx, inodeTree)) inodePtr, ok := tree.RebuiltAcquireItems(inodeCtx).Load(inodeWant.Key.Key()) tree.RebuiltReleaseItems() if !ok { diff --git a/cmd/btrfs-rec/inspect/rebuildtrees/util.go b/cmd/btrfs-rec/inspect/rebuildtrees/util.go index 842fb55..ee06394 100644 --- a/cmd/btrfs-rec/inspect/rebuildtrees/util.go +++ b/cmd/btrfs-rec/inspect/rebuildtrees/util.go @@ -19,3 +19,7 @@ func roundUp[T constraints.Integer](n, d T) T { func discardOK[T any](val T, _ bool) T { return val } + +func discardErr[T any](val T, _ error) T { + return val +} diff --git a/lib/btrfsutil/rebuilt_callbacks.go b/lib/btrfsutil/rebuilt_callbacks.go index 41fe7f1..fdc826c 100644 --- a/lib/btrfsutil/rebuilt_callbacks.go +++ b/lib/btrfsutil/rebuilt_callbacks.go @@ -32,8 +32,8 @@ func (noopRebuiltForrestCallbacks) AddedRoot(context.Context, btrfsprim.ObjID, b } func (cb noopRebuiltForrestCallbacks) LookupRoot(ctx context.Context, tree btrfsprim.ObjID) (offset btrfsprim.Generation, _item btrfsitem.Root, ok bool) { - rootTree := cb.forrest.RebuiltTree(ctx, btrfsprim.ROOT_TREE_OBJECTID) - if rootTree == nil { + rootTree, err := cb.forrest.RebuiltTree(ctx, btrfsprim.ROOT_TREE_OBJECTID) + if err != nil { return 0, btrfsitem.Root{}, false } tgt := btrfsprim.Key{ @@ -63,8 +63,8 @@ func (cb noopRebuiltForrestCallbacks) LookupRoot(ctx context.Context, tree btrfs } func (cb noopRebuiltForrestCallbacks) LookupUUID(ctx context.Context, uuid btrfsprim.UUID) (id btrfsprim.ObjID, ok bool) { - uuidTree := cb.forrest.RebuiltTree(ctx, btrfsprim.UUID_TREE_OBJECTID) - if uuidTree == nil { + uuidTree, err := cb.forrest.RebuiltTree(ctx, btrfsprim.UUID_TREE_OBJECTID) + if err != nil { return 0, false } tgt := btrfsitem.UUIDToKey(uuid) 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 } } diff --git a/lib/btrfsutil/rebuilt_forrest_test.go b/lib/btrfsutil/rebuilt_forrest_test.go new file mode 100644 index 0000000..6f80eff --- /dev/null +++ b/lib/btrfsutil/rebuilt_forrest_test.go @@ -0,0 +1,193 @@ +// Copyright (C) 2023 Luke Shumaker +// +// SPDX-License-Identifier: GPL-2.0-or-later + +package btrfsutil + +import ( + "context" + "testing" + + "github.com/datawire/dlib/dlog" + "github.com/stretchr/testify/assert" + + "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/btrfsvol" +) + +type rebuiltForrestCallbacks struct { + addedItem func(ctx context.Context, tree btrfsprim.ObjID, key btrfsprim.Key) + addedRoot func(ctx context.Context, tree btrfsprim.ObjID, root btrfsvol.LogicalAddr) + lookupRoot func(ctx context.Context, tree btrfsprim.ObjID) (offset btrfsprim.Generation, item btrfsitem.Root, ok bool) + lookupUUID func(ctx context.Context, uuid btrfsprim.UUID) (id btrfsprim.ObjID, ok bool) +} + +func (cbs rebuiltForrestCallbacks) AddedItem(ctx context.Context, tree btrfsprim.ObjID, key btrfsprim.Key) { + cbs.addedItem(ctx, tree, key) +} + +func (cbs rebuiltForrestCallbacks) AddedRoot(ctx context.Context, tree btrfsprim.ObjID, root btrfsvol.LogicalAddr) { + cbs.addedRoot(ctx, tree, root) +} + +func (cbs rebuiltForrestCallbacks) LookupRoot(ctx context.Context, tree btrfsprim.ObjID) (offset btrfsprim.Generation, item btrfsitem.Root, ok bool) { + return cbs.lookupRoot(ctx, tree) +} + +func (cbs rebuiltForrestCallbacks) LookupUUID(ctx context.Context, uuid btrfsprim.UUID) (id btrfsprim.ObjID, ok bool) { + return cbs.lookupUUID(ctx, uuid) +} + +func TestRebuiltTreeCycles(t *testing.T) { + t.Parallel() + + ctx := dlog.NewTestContext(t, true) + + type mockRoot struct { + ID btrfsprim.ObjID + UUID btrfsprim.UUID + ParentUUID btrfsprim.UUID + ParentGen btrfsprim.Generation + } + roots := []mockRoot{ + { + ID: 306, + UUID: btrfsprim.MustParseUUID("00000000-0000-0000-0000-000000000006"), + ParentUUID: btrfsprim.MustParseUUID("00000000-0000-0000-0000-000000000005"), + ParentGen: 1005, + }, + { + ID: 305, + UUID: btrfsprim.MustParseUUID("00000000-0000-0000-0000-000000000005"), + ParentUUID: btrfsprim.MustParseUUID("00000000-0000-0000-0000-000000000004"), + ParentGen: 1004, + }, + { + ID: 304, + UUID: btrfsprim.MustParseUUID("00000000-0000-0000-0000-000000000004"), + ParentUUID: btrfsprim.MustParseUUID("00000000-0000-0000-0000-000000000003"), + ParentGen: 1003, + }, + { + ID: 303, + UUID: btrfsprim.MustParseUUID("00000000-0000-0000-0000-000000000003"), + ParentUUID: btrfsprim.MustParseUUID("00000000-0000-0000-0000-000000000005"), + ParentGen: 1002, + }, + } + + cbs := rebuiltForrestCallbacks{ + addedItem: func(ctx context.Context, tree btrfsprim.ObjID, key btrfsprim.Key) { + // do nothing + }, + addedRoot: func(ctx context.Context, tree btrfsprim.ObjID, root btrfsvol.LogicalAddr) { + // do nothing + }, + lookupRoot: func(ctx context.Context, tree btrfsprim.ObjID) (offset btrfsprim.Generation, item btrfsitem.Root, ok bool) { + for _, root := range roots { + if root.ID == tree { + return root.ParentGen, btrfsitem.Root{ + Generation: 2000, + UUID: root.UUID, + ParentUUID: root.ParentUUID, + }, true + } + } + return 0, btrfsitem.Root{}, false + }, + lookupUUID: func(ctx context.Context, uuid btrfsprim.UUID) (id btrfsprim.ObjID, ok bool) { + for _, root := range roots { + if root.UUID == uuid { + return root.ID, true + } + } + return 0, false + }, + } + + rfs := NewRebuiltForrest(nil, Graph{}, cbs) + + tree, err := rfs.RebuiltTree(ctx, 306) + assert.EqualError(t, err, `loop detected: [306 305 304 303 305]`) + assert.Nil(t, tree) + + assert.NotNil(t, rfs.trees[305]) + tree, err = rfs.RebuiltTree(ctx, 305) + assert.EqualError(t, err, `loop detected: [305 304 303 305]`) + assert.Nil(t, tree) + + assert.NotNil(t, rfs.trees[304]) + tree, err = rfs.RebuiltTree(ctx, 304) + assert.EqualError(t, err, `loop detected: [304 303 305 304]`) + assert.Nil(t, tree) + + assert.NotNil(t, rfs.trees[303]) + tree, err = rfs.RebuiltTree(ctx, 303) + assert.EqualError(t, err, `loop detected: [303 305 304 303]`) + assert.Nil(t, tree) +} + +func TestRebuiltTreeParentErr(t *testing.T) { + t.Parallel() + + ctx := dlog.NewTestContext(t, true) + + type mockRoot struct { + ID btrfsprim.ObjID + UUID btrfsprim.UUID + ParentUUID btrfsprim.UUID + ParentGen btrfsprim.Generation + } + roots := []mockRoot{ + { + ID: 305, + UUID: btrfsprim.MustParseUUID("00000000-0000-0000-0000-000000000005"), + ParentUUID: btrfsprim.MustParseUUID("00000000-0000-0000-0000-000000000004"), + ParentGen: 1004, + }, + { + ID: 304, + UUID: btrfsprim.MustParseUUID("00000000-0000-0000-0000-000000000004"), + }, + } + + cbs := rebuiltForrestCallbacks{ + addedItem: func(ctx context.Context, tree btrfsprim.ObjID, key btrfsprim.Key) { + // do nothing + }, + addedRoot: func(ctx context.Context, tree btrfsprim.ObjID, root btrfsvol.LogicalAddr) { + // do nothing + }, + lookupRoot: func(ctx context.Context, tree btrfsprim.ObjID) (offset btrfsprim.Generation, item btrfsitem.Root, ok bool) { + if tree == 304 { + // Force a fault. + return 0, btrfsitem.Root{}, false + } + for _, root := range roots { + if root.ID == tree { + return root.ParentGen, btrfsitem.Root{ + Generation: 2000, + UUID: root.UUID, + ParentUUID: root.ParentUUID, + }, true + } + } + return 0, btrfsitem.Root{}, false + }, + lookupUUID: func(ctx context.Context, uuid btrfsprim.UUID) (id btrfsprim.ObjID, ok bool) { + for _, root := range roots { + if root.UUID == uuid { + return root.ID, true + } + } + return 0, false + }, + } + + 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.Nil(t, tree) +} diff --git a/lib/btrfsutil/rebuilt_tree.go b/lib/btrfsutil/rebuilt_tree.go index e507851..5d38bb1 100644 --- a/lib/btrfsutil/rebuilt_tree.go +++ b/lib/btrfsutil/rebuilt_tree.go @@ -23,6 +23,10 @@ import ( type RebuiltTree struct { // static + + rootErr error + ancestorLoop bool + ID btrfsprim.ObjID UUID btrfsprim.UUID Parent *RebuiltTree @@ -30,8 +34,11 @@ type RebuiltTree struct { forrest *RebuiltForrest // mutable - mu sync.RWMutex + + mu sync.RWMutex + Roots containers.Set[btrfsvol.LogicalAddr] + // There are 3 more mutable "members" that are protected by // `mu`; but they live in a shared Cache. They are all // derived from tree.Roots, which is why it's OK if they get -- cgit v1.1-4-g5e80 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(-) 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.1-4-g5e80 From 9a63a26b4e23a8977a9558b7e9a79792eb5b6d18 Mon Sep 17 00:00:00 2001 From: Luke Shumaker Date: Fri, 10 Mar 2023 19:31:50 -0700 Subject: cmd/btrfs-rec: Add a way to use RebuiltForrest instead of OldRebuiltForrest --- cmd/btrfs-rec/main.go | 27 ++++++++++++++++++++------- scripts/main.sh | 11 +++++++++++ 2 files changed, 31 insertions(+), 7 deletions(-) diff --git a/cmd/btrfs-rec/main.go b/cmd/btrfs-rec/main.go index da3aced..26857f0 100644 --- a/cmd/btrfs-rec/main.go +++ b/cmd/btrfs-rec/main.go @@ -49,9 +49,10 @@ var globalFlags struct { logLevel textui.LogLevelFlag pvs []string - mappings string - nodeList string - rebuild bool + mappings string + nodeList string + rebuildV1 bool + rebuildV2 bool stopProfiling profile.StopFunc @@ -101,8 +102,11 @@ func main() { "load node list (output of 'btrfs-recs inspect [rebuild-mappings] list-nodes') from external JSON file `nodes.json`") noError(argparser.MarkPersistentFlagFilename("node-list")) - argparser.PersistentFlags().BoolVar(&globalFlags.rebuild, "rebuild", false, - "attempt to rebuild broken btrees when reading") + argparser.PersistentFlags().BoolVar(&globalFlags.rebuildV1, "rebuild", false, + "attempt to rebuild broken btrees when reading (v1)") + + argparser.PersistentFlags().BoolVar(&globalFlags.rebuildV2, "rebuild-v2", false, + "attempt to rebuild broken btrees when reading (v2)") globalFlags.stopProfiling = profile.AddProfileFlags(argparser.PersistentFlags(), "profile.") @@ -210,15 +214,24 @@ func runWithRawFSAndNodeList(runE func(*btrfs.FS, []btrfsvol.LogicalAddr, *cobra func _runWithReadableFS(wantNodeList bool, runE func(btrfs.ReadableFS, []btrfsvol.LogicalAddr, *cobra.Command, []string) error) func(*cobra.Command, []string) error { inner := func(fs *btrfs.FS, nodeList []btrfsvol.LogicalAddr, cmd *cobra.Command, args []string) error { var rfs btrfs.ReadableFS = fs - if globalFlags.rebuild { + if globalFlags.rebuildV1 { rfs = btrfsutil.NewOldRebuiltForrest(fs) + } else if globalFlags.rebuildV2 { + ctx := cmd.Context() + + graph, err := btrfsutil.ReadGraph(ctx, fs, nodeList) + if err != nil { + return err + } + + rfs = btrfsutil.NewRebuiltForrest(fs, graph, nil) } return runE(rfs, nodeList, cmd, args) } return func(cmd *cobra.Command, args []string) error { - if wantNodeList { + if wantNodeList || globalFlags.rebuildV2 { return runWithRawFSAndNodeList(inner)(cmd, args) } return runWithRawFS(func(fs *btrfs.FS, cmd *cobra.Command, args []string) error { diff --git a/scripts/main.sh b/scripts/main.sh index c5fc238..c9c6f4e 100755 --- a/scripts/main.sh +++ b/scripts/main.sh @@ -80,7 +80,18 @@ run-btrfs-rec $gendir/4.ls-files.txt \ --mappings=$gendir/2.mappings.json \ --rebuild \ inspect ls-files +run-btrfs-rec $gendir/4.ls-files.v2.txt \ + --mappings=$gendir/2.mappings.json \ + --node-list=$gendir/0.nodes.json \ + --rebuild-v2 \ + inspect ls-files + run-btrfs-rec $gendir/4.ls-trees.txt \ --mappings=$gendir/2.mappings.json \ --node-list=$gendir/0.nodes.json \ inspect ls-trees +run-btrfs-rec $gendir/4.ls-trees.v2.txt \ + --mappings=$gendir/2.mappings.json \ + --node-list=$gendir/0.nodes.json \ + --rebuild-v2 \ + inspect ls-trees -- cgit v1.1-4-g5e80