diff options
author | Luke Shumaker <lukeshu@lukeshu.com> | 2023-04-17 21:46:53 -0600 |
---|---|---|
committer | Luke Shumaker <lukeshu@lukeshu.com> | 2023-04-17 21:46:53 -0600 |
commit | 72c0d02ebf69b12ab434a5243978f05a65c43e3b (patch) | |
tree | c37fbbb12d79b2d5c87a96f0e2770d22934eab91 /lib | |
parent | 4efa228eb104145bb0750fb68c0d9493dc5854d5 (diff) | |
parent | 7bd942c1e5f8d4a18f7e1ac866191d8f1aa31d30 (diff) |
Merge branch 'lukeshu/rebuilt-v2-pt3-errs'
Diffstat (limited to 'lib')
-rw-r--r-- | lib/btrfs/btrfstree/btree_tree.go | 3 | ||||
-rw-r--r-- | lib/btrfs/btrfstree/path.go | 6 | ||||
-rw-r--r-- | lib/btrfs/io3_btree.go | 3 | ||||
-rw-r--r-- | lib/btrfs/io4_fs.go | 2 | ||||
-rw-r--r-- | lib/btrfsutil/rebuilt_callbacks.go | 24 | ||||
-rw-r--r-- | lib/btrfsutil/rebuilt_forrest.go | 22 | ||||
-rw-r--r-- | lib/btrfsutil/rebuilt_forrest_test.go | 37 | ||||
-rw-r--r-- | lib/btrfsutil/rebuilt_tree.go | 301 | ||||
-rw-r--r-- | lib/textui/log.go | 8 |
9 files changed, 343 insertions, 63 deletions
diff --git a/lib/btrfs/btrfstree/btree_tree.go b/lib/btrfs/btrfstree/btree_tree.go index b9b9201..b071b7d 100644 --- a/lib/btrfs/btrfstree/btree_tree.go +++ b/lib/btrfs/btrfstree/btree_tree.go @@ -328,7 +328,8 @@ func (tree *RawTree) TreeParentID(ctx context.Context) (btrfsprim.ObjID, btrfspr } parentIDItem, err := uuidTree.TreeLookup(ctx, btrfsitem.UUIDToKey(tree.ParentUUID)) if err != nil { - return 0, 0, err + return 0, 0, fmt.Errorf("tree %s: failed to look up UUID: %v: %w", + tree.ID.Format(btrfsprim.ROOT_TREE_OBJECTID), tree.ParentUUID, err) } switch parentIDBody := parentIDItem.Body.(type) { case *btrfsitem.UUIDMap: diff --git a/lib/btrfs/btrfstree/path.go b/lib/btrfs/btrfstree/path.go index 327a39b..3fd43c8 100644 --- a/lib/btrfs/btrfstree/path.go +++ b/lib/btrfs/btrfstree/path.go @@ -134,7 +134,7 @@ func (path Path) String() string { return ret.String() } -func checkOwner( +func CheckOwner( ctx context.Context, forrest Forrest, treeID btrfsprim.ObjID, ownerToCheck btrfsprim.ObjID, genToCheck btrfsprim.Generation, ) error { @@ -194,7 +194,7 @@ func (path Path) NodeExpectations(ctx context.Context) (_ btrfsvol.LogicalAddr, Level: containers.OptionalValue(lastElem.ToLevel), Generation: containers.OptionalValue(lastElem.ToGeneration), Owner: func(owner btrfsprim.ObjID, gen btrfsprim.Generation) error { - return checkOwner(ctx, firstElem.Forrest, lastElem.TreeID, + return CheckOwner(ctx, firstElem.Forrest, lastElem.TreeID, owner, gen) }, MinItem: containers.OptionalValue(btrfsprim.Key{}), @@ -206,7 +206,7 @@ func (path Path) NodeExpectations(ctx context.Context) (_ btrfsvol.LogicalAddr, Level: containers.OptionalValue(lastElem.ToLevel), Generation: containers.OptionalValue(lastElem.ToGeneration), Owner: func(owner btrfsprim.ObjID, gen btrfsprim.Generation) error { - return checkOwner(ctx, firstElem.Forrest, lastElem.FromTree, + return CheckOwner(ctx, firstElem.Forrest, lastElem.FromTree, owner, gen) }, MinItem: containers.OptionalValue(lastElem.ToMinKey), diff --git a/lib/btrfs/io3_btree.go b/lib/btrfs/io3_btree.go index c9e1d79..7518561 100644 --- a/lib/btrfs/io3_btree.go +++ b/lib/btrfs/io3_btree.go @@ -6,7 +6,6 @@ package btrfs import ( "context" - "fmt" "git.lukeshu.com/btrfs-progs-ng/lib/btrfs/btrfsprim" "git.lukeshu.com/btrfs-progs-ng/lib/btrfs/btrfstree" @@ -44,7 +43,7 @@ func (fs *FS) AcquireNode(ctx context.Context, addr btrfsvol.LogicalAddr, exp bt if nodeEntry.node != nil { if err := exp.Check(nodeEntry.node); err != nil { fs.cacheNodes.Release(addr) - return nil, fmt.Errorf("btrfs.FS.AcquireNode: node@%v: %w", addr, err) + return nil, err } } diff --git a/lib/btrfs/io4_fs.go b/lib/btrfs/io4_fs.go index 9b70713..1b7837e 100644 --- a/lib/btrfs/io4_fs.go +++ b/lib/btrfs/io4_fs.go @@ -423,7 +423,7 @@ func (sv *Subvolume) loadFile(_ context.Context, inode btrfsprim.ObjID, file *Fi if err != nil { file.Errs = append(file.Errs, fmt.Errorf("extent %v: %w", extent.OffsetWithinFile, err)) } - pos += size + pos = extent.OffsetWithinFile + size } if file.InodeItem != nil && pos != file.InodeItem.NumBytes { if file.InodeItem.NumBytes > pos { diff --git a/lib/btrfsutil/rebuilt_callbacks.go b/lib/btrfsutil/rebuilt_callbacks.go index 0b51d08..b5fbc91 100644 --- a/lib/btrfsutil/rebuilt_callbacks.go +++ b/lib/btrfsutil/rebuilt_callbacks.go @@ -16,8 +16,8 @@ import ( type RebuiltForrestCallbacks interface { 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) + LookupRoot(ctx context.Context, tree btrfsprim.ObjID) (offset btrfsprim.Generation, item btrfsitem.Root, err error) + LookupUUID(ctx context.Context, uuid btrfsprim.UUID) (id btrfsprim.ObjID, err error) } type RebuiltForrestExtendedCallbacks interface { @@ -32,21 +32,21 @@ type noopRebuiltForrestCallbacks struct { func (noopRebuiltForrestCallbacks) AddedRoot(context.Context, btrfsprim.ObjID, btrfsvol.LogicalAddr) { } -func (cb noopRebuiltForrestCallbacks) LookupRoot(ctx context.Context, tree btrfsprim.ObjID) (offset btrfsprim.Generation, _item btrfsitem.Root, ok bool) { +func (cb noopRebuiltForrestCallbacks) LookupRoot(ctx context.Context, tree btrfsprim.ObjID) (offset btrfsprim.Generation, _item btrfsitem.Root, err error) { rootTree, err := cb.forrest.ForrestLookup(ctx, btrfsprim.ROOT_TREE_OBJECTID) if err != nil { - return 0, btrfsitem.Root{}, false + return 0, btrfsitem.Root{}, err } item, err := rootTree.TreeSearch(ctx, btrfstree.SearchRootItem(tree)) if err != nil { - return 0, btrfsitem.Root{}, false + return 0, btrfsitem.Root{}, err } defer item.Body.Free() switch itemBody := item.Body.(type) { case *btrfsitem.Root: - return btrfsprim.Generation(item.Key.Offset), *itemBody, true + return btrfsprim.Generation(item.Key.Offset), *itemBody, nil case *btrfsitem.Error: - return 0, btrfsitem.Root{}, false + return 0, btrfsitem.Root{}, itemBody.Err default: // This is a panic because the item decoder should not emit ROOT_ITEM items as anything but // btrfsitem.Root or btrfsitem.Error without this code also being updated. @@ -54,22 +54,22 @@ func (cb noopRebuiltForrestCallbacks) LookupRoot(ctx context.Context, tree btrfs } } -func (cb noopRebuiltForrestCallbacks) LookupUUID(ctx context.Context, uuid btrfsprim.UUID) (id btrfsprim.ObjID, ok bool) { +func (cb noopRebuiltForrestCallbacks) LookupUUID(ctx context.Context, uuid btrfsprim.UUID) (id btrfsprim.ObjID, err error) { uuidTree, err := cb.forrest.ForrestLookup(ctx, btrfsprim.UUID_TREE_OBJECTID) if err != nil { - return 0, false + return 0, err } tgt := btrfsitem.UUIDToKey(uuid) item, err := uuidTree.TreeLookup(ctx, tgt) if err != nil { - return 0, false + return 0, err } defer item.Body.Free() switch itemBody := item.Body.(type) { case *btrfsitem.UUIDMap: - return itemBody.ObjID, true + return itemBody.ObjID, nil case *btrfsitem.Error: - return 0, false + return 0, itemBody.Err default: // This is a panic because the item decoder should not emit UUID_SUBVOL items as anything but // btrfsitem.UUIDMap or btrfsitem.Error without this code also being updated. diff --git a/lib/btrfsutil/rebuilt_forrest.go b/lib/btrfsutil/rebuilt_forrest.go index 900e725..79d8beb 100644 --- a/lib/btrfsutil/rebuilt_forrest.go +++ b/lib/btrfsutil/rebuilt_forrest.go @@ -212,19 +212,24 @@ func (ts *RebuiltForrest) rebuildTree(ctx context.Context, treeID btrfsprim.ObjI sb, _ := ts.Superblock() ts.trees[treeID].Root = sb.BlockGroupRoot default: - rootOff, rootItem, ok := ts.cb.LookupRoot(ctx, treeID) - if !ok { - ts.trees[treeID].rootErr = btrfstree.ErrNoTree + rootOff, rootItem, err := ts.cb.LookupRoot(ctx, treeID) + if err != nil { + ts.trees[treeID].rootErr = fmt.Errorf("tree %s: %w: %s", + treeID.Format(btrfsprim.ROOT_TREE_OBJECTID), btrfstree.ErrNoTree, err) return } ts.trees[treeID].Root = rootItem.ByteNr ts.trees[treeID].UUID = rootItem.UUID if rootItem.ParentUUID != (btrfsprim.UUID{}) { ts.trees[treeID].ParentGen = rootOff - parentID, ok := ts.cb.LookupUUID(ctx, rootItem.ParentUUID) - if !ok { - if !ts.laxAncestors { - ts.trees[treeID].rootErr = fmt.Errorf("failed to look up UUID: %v", rootItem.ParentUUID) + parentID, err := ts.cb.LookupUUID(ctx, rootItem.ParentUUID) + if err != nil { + err := fmt.Errorf("tree %s: failed to look up UUID: %v: %w", + treeID.Format(btrfsprim.ROOT_TREE_OBJECTID), rootItem.ParentUUID, err) + if ts.laxAncestors { + ts.trees[treeID].parentErr = err + } else { + ts.trees[treeID].rootErr = err } return } @@ -235,7 +240,8 @@ func (ts *RebuiltForrest) rebuildTree(ctx context.Context, treeID btrfsprim.ObjI ts.trees[treeID].ancestorLoop = true return case !ts.laxAncestors && 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) + ts.trees[treeID].rootErr = fmt.Errorf("tree %s: failed to rebuild parent: %w", + treeID.Format(btrfsprim.ROOT_TREE_OBJECTID), ts.trees[treeID].Parent.rootErr) return } } diff --git a/lib/btrfsutil/rebuilt_forrest_test.go b/lib/btrfsutil/rebuilt_forrest_test.go index 8bbb50a..bb7b698 100644 --- a/lib/btrfsutil/rebuilt_forrest_test.go +++ b/lib/btrfsutil/rebuilt_forrest_test.go @@ -13,14 +13,15 @@ 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" ) 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) + lookupRoot func(ctx context.Context, tree btrfsprim.ObjID) (offset btrfsprim.Generation, item btrfsitem.Root, err error) + lookupUUID func(ctx context.Context, uuid btrfsprim.UUID) (id btrfsprim.ObjID, err error) } func (cbs rebuiltForrestCallbacks) AddedItem(ctx context.Context, tree btrfsprim.ObjID, key btrfsprim.Key) { @@ -31,11 +32,11 @@ func (cbs rebuiltForrestCallbacks) AddedRoot(ctx context.Context, tree btrfsprim cbs.addedRoot(ctx, tree, root) } -func (cbs rebuiltForrestCallbacks) LookupRoot(ctx context.Context, tree btrfsprim.ObjID) (offset btrfsprim.Generation, item btrfsitem.Root, ok bool) { +func (cbs rebuiltForrestCallbacks) LookupRoot(ctx context.Context, tree btrfsprim.ObjID) (offset btrfsprim.Generation, item btrfsitem.Root, err error) { return cbs.lookupRoot(ctx, tree) } -func (cbs rebuiltForrestCallbacks) LookupUUID(ctx context.Context, uuid btrfsprim.UUID) (id btrfsprim.ObjID, ok bool) { +func (cbs rebuiltForrestCallbacks) LookupUUID(ctx context.Context, uuid btrfsprim.UUID) (id btrfsprim.ObjID, err error) { return cbs.lookupUUID(ctx, uuid) } @@ -84,25 +85,25 @@ func TestRebuiltTreeCycles(t *testing.T) { 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) { + lookupRoot: func(ctx context.Context, tree btrfsprim.ObjID) (offset btrfsprim.Generation, item btrfsitem.Root, err error) { for _, root := range roots { if root.ID == tree { return root.ParentGen, btrfsitem.Root{ Generation: 2000, UUID: root.UUID, ParentUUID: root.ParentUUID, - }, true + }, nil } } - return 0, btrfsitem.Root{}, false + return 0, btrfsitem.Root{}, btrfstree.ErrNoItem }, - lookupUUID: func(ctx context.Context, uuid btrfsprim.UUID) (id btrfsprim.ObjID, ok bool) { + lookupUUID: func(ctx context.Context, uuid btrfsprim.UUID) (id btrfsprim.ObjID, err error) { for _, root := range roots { if root.UUID == uuid { - return root.ID, true + return root.ID, nil } } - return 0, false + return 0, btrfstree.ErrNoItem }, } @@ -193,10 +194,10 @@ func TestRebuiltTreeParentErr(t *testing.T) { 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) { + lookupRoot: func(ctx context.Context, tree btrfsprim.ObjID) (offset btrfsprim.Generation, item btrfsitem.Root, err error) { if tree == 304 { // Force a fault. - return 0, btrfsitem.Root{}, false + return 0, btrfsitem.Root{}, btrfstree.ErrNoItem } for _, root := range roots { if root.ID == tree { @@ -204,18 +205,18 @@ func TestRebuiltTreeParentErr(t *testing.T) { Generation: 2000, UUID: root.UUID, ParentUUID: root.ParentUUID, - }, true + }, nil } } - return 0, btrfsitem.Root{}, false + return 0, btrfsitem.Root{}, btrfstree.ErrNoItem }, - lookupUUID: func(ctx context.Context, uuid btrfsprim.UUID) (id btrfsprim.ObjID, ok bool) { + lookupUUID: func(ctx context.Context, uuid btrfsprim.UUID) (id btrfsprim.ObjID, err error) { for _, root := range roots { if root.UUID == uuid { - return root.ID, true + return root.ID, nil } } - return 0, false + return 0, btrfstree.ErrNoItem }, } @@ -224,7 +225,7 @@ func TestRebuiltTreeParentErr(t *testing.T) { rfs := NewRebuiltForrest(nil, Graph{}, cbs, false) tree, err := rfs.RebuiltTree(ctx, 305) - assert.EqualError(t, err, `failed to rebuild parent tree: 304: tree does not exist`) + assert.EqualError(t, err, `tree 305: failed to rebuild parent: tree 304: tree does not exist: item does not exist`) assert.Nil(t, tree) }) diff --git a/lib/btrfsutil/rebuilt_tree.go b/lib/btrfsutil/rebuilt_tree.go index 3036938..97308a3 100644 --- a/lib/btrfsutil/rebuilt_tree.go +++ b/lib/btrfsutil/rebuilt_tree.go @@ -10,6 +10,7 @@ import ( "sync" "time" + "github.com/datawire/dlib/derror" "github.com/datawire/dlib/dlog" "git.lukeshu.com/btrfs-progs-ng/lib/btrfs/btrfsitem" @@ -34,6 +35,7 @@ type RebuiltTree struct { Root btrfsvol.LogicalAddr Parent *RebuiltTree ParentGen btrfsprim.Generation // offset of this tree's root item + parentErr error forrest *RebuiltForrest // mutable @@ -44,7 +46,7 @@ type RebuiltTree struct { Roots containers.Set[btrfsvol.LogicalAddr] - // There are 3 more mutable "members" that are protected by + // There are 4 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 // evicted. @@ -52,12 +54,14 @@ type RebuiltTree struct { // 1. tree.acquireNodeIndex() = tree.forrest.nodeIndex.Acquire(tree.ID) // 2. tree.RebuiltAcquireItems() = tree.forrest.incItems.Acquire(tree.ID) // 3. tree.RebuiltAcquirePotentialItems() = tree.forrest.excItems.Acquire(tree.ID) + // 4. tree.addErrs() = tree.forrest.errors.Acquire(tree.ID) } type rebuiltSharedCache struct { nodeIndex containers.Cache[btrfsprim.ObjID, rebuiltNodeIndex] incItems containers.Cache[btrfsprim.ObjID, containers.SortedMap[btrfsprim.Key, ItemPtr]] excItems containers.Cache[btrfsprim.ObjID, containers.SortedMap[btrfsprim.Key, ItemPtr]] + errors containers.Cache[btrfsprim.ObjID, containers.IntervalTree[btrfsprim.Key, rebuiltTreeError]] } func makeRebuiltSharedCache(forrest *RebuiltForrest) rebuiltSharedCache { @@ -80,6 +84,12 @@ func makeRebuiltSharedCache(forrest *RebuiltForrest) rebuiltSharedCache { func(ctx context.Context, treeID btrfsprim.ObjID, excItems *containers.SortedMap[btrfsprim.Key, ItemPtr]) { *excItems = forrest.trees[treeID].uncachedExcItems(ctx) })) + ret.errors = containers.NewARCache[btrfsprim.ObjID, containers.IntervalTree[btrfsprim.Key, rebuiltTreeError]]( + textui.Tunable(8), + containers.SourceFunc[btrfsprim.ObjID, containers.IntervalTree[btrfsprim.Key, rebuiltTreeError]]( + func(ctx context.Context, treeID btrfsprim.ObjID, errs *containers.IntervalTree[btrfsprim.Key, rebuiltTreeError]) { + *errs = forrest.trees[treeID].uncachedErrors(ctx) + })) return ret } @@ -386,6 +396,249 @@ func (tree *RebuiltTree) uncachedItems(ctx context.Context, inc bool) containers return index } +// evictable member 4: .addErrs() ////////////////////////////////////////////////////////////////////////////////////// + +type rebuiltTreeError struct { + Min btrfsprim.Key + Max btrfsprim.Key + Node btrfsvol.LogicalAddr + Err error +} + +func (e rebuiltTreeError) Error() string { + return fmt.Sprintf("keys %v-%v: node@%v: %v", e.Min, e.Max, e.Node, e.Err) +} + +func (e rebuiltTreeError) Unwrap() error { + return e.Err +} + +type errorStats struct { + Nodes textui.Portion[int] + NumErrs int +} + +func (s errorStats) String() string { + return textui.Sprintf("%v (%v errs)", + s.Nodes, s.NumErrs) +} + +func (tree *RebuiltTree) uncachedErrors(ctx context.Context) containers.IntervalTree[btrfsprim.Key, rebuiltTreeError] { + ctx = dlog.WithField(ctx, "btrfs.util.rebuilt-tree.index-errors", fmt.Sprintf("tree=%v", tree.ID)) + + tree.mu.RLock() + defer tree.mu.RUnlock() + + errs := containers.IntervalTree[btrfsprim.Key, rebuiltTreeError]{ + MinFn: func(err rebuiltTreeError) btrfsprim.Key { + return err.Min + }, + MaxFn: func(err rebuiltTreeError) btrfsprim.Key { + return err.Max + }, + } + + nodeIndex := tree.acquireNodeIndex(ctx) + defer tree.releaseNodeIndex() + + nodesToProcess := make(containers.Set[btrfsvol.LogicalAddr], len(nodeIndex.nodeToRoots)) + for node := range nodeIndex.nodeToRoots { + if !maps.HaveAnyKeysInCommon(nodeIndex.nodeToRoots[node], tree.Roots) { + continue + } + nodesToProcess.Insert(node) + for _, kp := range tree.forrest.graph.EdgesFrom[node] { + nodesToProcess.Insert(kp.ToNode) + } + } + for root := range tree.Roots { + // For BadNodes that are roots. + nodesToProcess.Insert(root) + } + + var stats errorStats + stats.Nodes.D = len(nodesToProcess) + progressWriter := textui.NewProgress[errorStats](ctx, dlog.LogLevelInfo, textui.Tunable(1*time.Second)) + progressWriter.Set(stats) + + var kps []*GraphEdge + for i, node := range maps.SortedKeys(nodesToProcess) { + stats.Nodes.N = i + progressWriter.Set(stats) + + // `node` may either be in the tree, or just pointed + // to by a different node in the tree. Decide whether + // it's in the tree, and gather all of the + // key-pointers in the tree that point to it. + inTree := maps.HaveAnyKeysInCommon(nodeIndex.nodeToRoots[node], tree.Roots) + kps = kps[:0] + for _, kp := range tree.forrest.graph.EdgesTo[node] { + if !maps.HaveAnyKeysInCommon(nodeIndex.nodeToRoots[kp.FromNode], tree.Roots) { + continue + } + kps = append(kps, kp) + } + + // Look at all key-pointers to decide what our + // expectations are. + var ( + expLevel = make(containers.Set[uint8], len(kps)) + expGen = make(containers.Set[btrfsprim.Generation], len(kps)) + expTree = make(containers.Set[btrfsprim.ObjID], len(kps)) + loMinItem = btrfsprim.MaxKey // lowest kp.ToKey seen + hiMinItem = btrfsprim.Key{} // highest kp.ToKey seen + loMaxItem = btrfsprim.MaxKey // lowest nodeToRoots[node][root] seen + hiMaxItem = btrfsprim.Key{} // highest nodeToRoots[node][root] seen + ) + expTree.Insert(tree.ID) + if len(kps) == 0 { + // This is a root. + loMinItem = btrfsprim.Key{} + hiMaxItem = btrfsprim.MaxKey + } else { + // expLevel, expGen, loMinItem, hiMinItem, + for _, kp := range kps { + expLevel.Insert(kp.ToLevel) + expGen.Insert(kp.ToGeneration) + expTree.Insert(kp.FromTree) + if kp.ToKey.Compare(loMinItem) < 0 { + loMinItem = kp.ToKey + } + if kp.ToKey.Compare(hiMinItem) > 0 { + hiMinItem = kp.ToKey + } + } + // loMaxItem, hiMaxItem + if !inTree { + for _, kp := range kps { + for root, rootInfo := range nodeIndex.nodeToRoots[kp.FromNode] { + if !tree.Roots.Has(root) { + continue + } + if kp.FromSlot+1 < len(tree.forrest.graph.EdgesFrom[kp.FromNode]) { + rootInfo.loMaxItem = tree.forrest.graph.EdgesFrom[kp.FromNode][kp.FromSlot+1].ToKey.Mm() + rootInfo.hiMaxItem = rootInfo.loMaxItem + } + if loMaxItem.Compare(rootInfo.loMaxItem) > 0 { + loMaxItem = rootInfo.loMaxItem + } + if hiMaxItem.Compare(rootInfo.hiMaxItem) < 0 { + hiMaxItem = rootInfo.hiMaxItem + } + } + } + } else { + // As an optimization, we can look at this node's rootInfo directly. + // This should be equivalent to the above loop for `!inTree`, but is + // faster. + for root, rootInfo := range nodeIndex.nodeToRoots[node] { + if !tree.Roots.Has(root) { + continue + } + if loMaxItem.Compare(rootInfo.loMaxItem) > 0 { + loMaxItem = rootInfo.loMaxItem + } + if hiMaxItem.Compare(rootInfo.hiMaxItem) < 0 { + hiMaxItem = rootInfo.hiMaxItem + } + } + } + } + + // Assemble all of that in to a btrfstree.NodeExpectations. + var nodeErrs derror.MultiError + exp := btrfstree.NodeExpectations{ + LAddr: containers.OptionalValue(node), + MinItem: containers.OptionalValue(hiMinItem), + MaxItem: containers.OptionalValue(loMaxItem), + Owner: func(owner btrfsprim.ObjID, gen btrfsprim.Generation) error { + byStr := make(map[string]error) + for _, kpTree := range maps.SortedKeys(expTree) { + if err := btrfstree.CheckOwner(ctx, tree.forrest, kpTree, owner, gen); err != nil { + byStr[err.Error()] = err + } + } + if len(byStr) > 0 { + byPos := make(derror.MultiError, 0, len(byStr)) + for _, str := range maps.SortedKeys(byStr) { + byPos = append(byPos, byStr[str]) + } + return byPos + } + return nil + }, + } + switch len(expLevel) { + case 0: + // do nothing + case 1: + exp.Level = containers.OptionalValue(expLevel.TakeOne()) + default: + nodeErrs = append(nodeErrs, + fmt.Errorf("multiple KPs request different node levels: %v (actual: %v)", + maps.SortedKeys(expLevel), tree.forrest.graph.Nodes[node].Level)) + } + switch len(expGen) { + case 0: + // do nothing + case 1: + exp.Generation = containers.OptionalValue(expGen.TakeOne()) + default: + nodeErrs = append(nodeErrs, + fmt.Errorf("multiple KPs request different node generations: %v (actual: %v)", + maps.SortedKeys(expGen), tree.forrest.graph.Nodes[node].Generation)) + } + + // Check those expectations. + if hiMaxItem.Compare(loMinItem) < 0 { + nodeErrs = append(nodeErrs, + fmt.Errorf("loMinItem:%v > hiMaxItem:%v", loMinItem, hiMaxItem)) + loMinItem = btrfsprim.Key{} + hiMaxItem = btrfsprim.MaxKey + } + if err := tree.forrest.graph.BadNodes[node]; err != nil { + nodeErrs = append(nodeErrs, err) + } else if err := tree.forrest.graph.Nodes[node].CheckExpectations(tree.forrest.graph, exp); err != nil { + nodeErrs = append(nodeErrs, err) + } + + if len(nodeErrs) > 0 { + errs.Insert(rebuiltTreeError{ + Min: loMinItem, + Max: hiMaxItem, + Node: node, + Err: nodeErrs, + }) + + stats.NumErrs++ + progressWriter.Set(stats) + } + } + stats.Nodes.N = stats.Nodes.D + progressWriter.Set(stats) + progressWriter.Done() + + return errs +} + +func (tree *RebuiltTree) addErrs(ctx context.Context, fn func(btrfsprim.Key, uint32) int, err error) error { + var errs derror.MultiError + tree.forrest.errors.Acquire(ctx, tree.ID).Subrange( + func(k btrfsprim.Key) int { return fn(k, 0) }, + func(v rebuiltTreeError) bool { + errs = append(errs, v) + return true + }) + tree.forrest.errors.Release(tree.ID) + if len(errs) == 0 { + return err + } + if err != nil { + errs = append(errs, err) + } + return errs +} + // main public API ///////////////////////////////////////////////////////////////////////////////////////////////////// func (tree *RebuiltTree) RebuiltShouldReplace(oldNode, newNode btrfsvol.LogicalAddr) bool { @@ -496,6 +749,7 @@ func (tree *RebuiltTree) RebuiltAddRoot(ctx context.Context, rootNode btrfsvol.L tree.Roots.Insert(rootNode) tree.forrest.incItems.Delete(tree.ID) // force re-gen tree.forrest.excItems.Delete(tree.ID) // force re-gen + tree.forrest.errors.Delete(tree.ID) // force re-gen if shouldFlush { tree.forrest.flushNegativeCache(ctx) @@ -506,11 +760,12 @@ func (tree *RebuiltTree) RebuiltAddRoot(ctx context.Context, rootNode btrfsvol.L // RebuiltCOWDistance returns how many COW-snapshots down the 'tree' // is from the 'parent'. func (tree *RebuiltTree) RebuiltCOWDistance(parentID btrfsprim.ObjID) (dist int, ok bool) { + root := tree.ancestorRoot for { if parentID == tree.ID { return dist, true } - if tree.Parent == nil { + if tree.Parent == nil || tree.ID == root { return 0, false } tree = tree.Parent @@ -552,15 +807,17 @@ var _ btrfstree.Tree = (*RebuiltTree)(nil) // TreeParentID implements btrfstree.Tree. func (tree *RebuiltTree) TreeParentID(_ context.Context) (btrfsprim.ObjID, btrfsprim.Generation, error) { - if tree.Parent == nil { + switch { + case tree.parentErr != nil: + return 0, 0, tree.parentErr + case tree.Parent == nil: return 0, 0, nil + default: + return tree.Parent.ID, tree.ParentGen, 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)) } @@ -568,16 +825,19 @@ func (tree *RebuiltTree) TreeLookup(ctx context.Context, key btrfsprim.Key) (btr // 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) { + tree.forrest.commitTrees(ctx, tree.ID) + tree.initRoots(ctx) + tree.mu.RLock() + defer tree.mu.RUnlock() + _, 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 btrfstree.Item{}, fmt.Errorf("item with %s: %w", searcher, tree.addErrs(ctx, searcher.Search, btrfstree.ErrNoItem)) } return tree.forrest.readItem(ctx, ptr), nil } @@ -585,26 +845,32 @@ func (tree *RebuiltTree) TreeSearch(ctx context.Context, searcher btrfstree.Tree // 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.forrest.commitTrees(ctx, tree.ID) + tree.initRoots(ctx) + tree.mu.RLock() + defer tree.mu.RUnlock() + tree.RebuiltAcquireItems(ctx).Range(func(_ btrfsprim.Key, ptr ItemPtr) bool { return handleFn(tree.forrest.readItem(ctx, ptr)) }) tree.RebuiltReleaseItems() - return nil + return tree.addErrs(ctx, func(btrfsprim.Key, uint32) int { return 0 }, 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 { + tree.forrest.commitTrees(ctx, tree.ID) + tree.initRoots(ctx) + tree.mu.RLock() + defer tree.mu.RUnlock() + var cnt int tree.RebuiltAcquireItems(ctx).Subrange( func(_ btrfsprim.Key, ptr ItemPtr) int { @@ -618,8 +884,13 @@ func (tree *RebuiltTree) TreeSubrange(ctx context.Context, ) tree.RebuiltReleaseItems() + var err error if cnt < min { - return btrfstree.ErrNoItem + err = btrfstree.ErrNoItem + } + err = tree.addErrs(ctx, searcher.Search, err) + if err != nil { + return fmt.Errorf("items with %s: %w", searcher, err) } return nil diff --git a/lib/textui/log.go b/lib/textui/log.go index 25bb4be..a26dd5f 100644 --- a/lib/textui/log.go +++ b/lib/textui/log.go @@ -338,12 +338,14 @@ func fieldOrd(key string) int { // btrfsutil.RebuiltForrest //////////////////////////////////////////// case "btrfs.util.rebuilt-forrest.add-tree": - return -7 + return -8 case "btrfs.util.rebuilt-forrest.add-tree.want.key": - return -6 + return -7 case "btrfs.util.rebuilt-forrest.add-tree.want.reason": - return -5 + return -6 case "btrfs.util.rebuilt-tree.add-root": + return -5 + case "btrfs.util.rebuilt-tree.index-errors": return -4 case "btrfs.util.rebuilt-tree.index-inc-items": return -3 |