diff options
Diffstat (limited to 'lib/btrfsprogs/btrfsinspect/rebuildnodes/rebuild_wantcb.go')
| -rw-r--r-- | lib/btrfsprogs/btrfsinspect/rebuildnodes/rebuild_wantcb.go | 400 |
1 files changed, 0 insertions, 400 deletions
diff --git a/lib/btrfsprogs/btrfsinspect/rebuildnodes/rebuild_wantcb.go b/lib/btrfsprogs/btrfsinspect/rebuildnodes/rebuild_wantcb.go deleted file mode 100644 index adf3cff..0000000 --- a/lib/btrfsprogs/btrfsinspect/rebuildnodes/rebuild_wantcb.go +++ /dev/null @@ -1,400 +0,0 @@ -// Copyright (C) 2022-2023 Luke Shumaker <lukeshu@lukeshu.com> -// -// SPDX-License-Identifier: GPL-2.0-or-later - -package rebuildnodes - -import ( - "bytes" - "context" - "fmt" - - "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/btrfssum" - "git.lukeshu.com/btrfs-progs-ng/lib/btrfs/btrfsvol" - "git.lukeshu.com/btrfs-progs-ng/lib/btrfsprogs/btrfsinspect/rebuildnodes/keyio" - "git.lukeshu.com/btrfs-progs-ng/lib/containers" -) - -// fsErr implements rebuildCallbacks. -func (o *rebuilder) fsErr(ctx context.Context, e error) { - dlog.Errorf(ctx, "filesystem error: %v", e) -} - -// want implements rebuildCallbacks. -func (o *rebuilder) want(ctx context.Context, reason string, treeID btrfsprim.ObjID, objID btrfsprim.ObjID, typ btrfsprim.ItemType) { - wantKey := WantWithTree{ - TreeID: treeID, - Key: Want{ - ObjectID: objID, - ItemType: typ, - OffsetType: offsetAny, - }, - } - ctx = withWant(ctx, logFieldItemWant, reason, wantKey) - o._want(ctx, wantKey) -} - -func (o *rebuilder) _want(ctx context.Context, wantKey WantWithTree) (key btrfsprim.Key, ok bool) { - if o.rebuilt.Tree(ctx, wantKey.TreeID) == nil { - o.enqueueRetry(wantKey.TreeID) - return btrfsprim.Key{}, false - } - - // check if we already have it - - tgt := wantKey.Key.Key() - if key, _, ok := o.rebuilt.Tree(ctx, wantKey.TreeID).Items(ctx).Search(func(key btrfsprim.Key, _ keyio.ItemPtr) int { - key.Offset = 0 - return tgt.Compare(key) - }); ok { - return key, true - } - - // OK, we need to insert it - - if o.hasAugment(wantKey) { - return btrfsprim.Key{}, false - } - wants := make(containers.Set[btrfsvol.LogicalAddr]) - o.rebuilt.Tree(ctx, wantKey.TreeID).PotentialItems(ctx).Subrange( - func(k btrfsprim.Key, _ keyio.ItemPtr) int { - k.Offset = 0 - return tgt.Compare(k) - }, - func(_ btrfsprim.Key, v keyio.ItemPtr) bool { - wants.InsertFrom(o.rebuilt.Tree(ctx, wantKey.TreeID).LeafToRoots(ctx, v.Node)) - return true - }) - o.wantAugment(ctx, wantKey, wants) - return btrfsprim.Key{}, false -} - -// wantOff implements rebuildCallbacks. -func (o *rebuilder) wantOff(ctx context.Context, reason string, treeID btrfsprim.ObjID, objID btrfsprim.ObjID, typ btrfsprim.ItemType, off uint64) { - wantKey := WantWithTree{ - TreeID: treeID, - Key: Want{ - ObjectID: objID, - ItemType: typ, - OffsetType: offsetExact, - OffsetLow: off, - }, - } - ctx = withWant(ctx, logFieldItemWant, reason, wantKey) - o._wantOff(ctx, wantKey) -} - -func (o *rebuilder) _wantOff(ctx context.Context, wantKey WantWithTree) (ok bool) { - if o.rebuilt.Tree(ctx, wantKey.TreeID) == nil { - o.enqueueRetry(wantKey.TreeID) - return false - } - - // check if we already have it - - tgt := wantKey.Key.Key() - if _, ok := o.rebuilt.Tree(ctx, wantKey.TreeID).Items(ctx).Load(tgt); ok { - return true - } - - // OK, we need to insert it - - if o.hasAugment(wantKey) { - return false - } - wants := make(containers.Set[btrfsvol.LogicalAddr]) - o.rebuilt.Tree(ctx, wantKey.TreeID).PotentialItems(ctx).Subrange( - func(k btrfsprim.Key, _ keyio.ItemPtr) int { return tgt.Compare(k) }, - func(_ btrfsprim.Key, v keyio.ItemPtr) bool { - wants.InsertFrom(o.rebuilt.Tree(ctx, wantKey.TreeID).LeafToRoots(ctx, v.Node)) - return true - }) - o.wantAugment(ctx, wantKey, wants) - return false -} - -// wantDirIndex implements rebuildCallbacks. -func (o *rebuilder) wantDirIndex(ctx context.Context, reason string, treeID btrfsprim.ObjID, objID btrfsprim.ObjID, name []byte) { - wantKey := WantWithTree{ - TreeID: treeID, - Key: Want{ - ObjectID: objID, - ItemType: btrfsitem.DIR_INDEX_KEY, - OffsetType: offsetName, - OffsetName: string(name), - }, - } - ctx = withWant(ctx, logFieldItemWant, reason, wantKey) - - if o.rebuilt.Tree(ctx, treeID) == nil { - o.enqueueRetry(treeID) - return - } - - // check if we already have it - - tgt := wantKey.Key.Key() - found := false - o.rebuilt.Tree(ctx, treeID).Items(ctx).Subrange( - func(key btrfsprim.Key, _ keyio.ItemPtr) int { - key.Offset = 0 - return tgt.Compare(key) - }, - func(_ btrfsprim.Key, ptr keyio.ItemPtr) bool { - if itemName, ok := o.keyIO.Names[ptr]; ok && bytes.Equal(itemName, name) { - found = true - } - return !found - }) - if found { - return - } - - // OK, we need to insert it - - if o.hasAugment(wantKey) { - return - } - wants := make(containers.Set[btrfsvol.LogicalAddr]) - o.rebuilt.Tree(ctx, treeID).PotentialItems(ctx).Subrange( - func(key btrfsprim.Key, _ keyio.ItemPtr) int { - key.Offset = 0 - return tgt.Compare(key) - }, - func(_ btrfsprim.Key, ptr keyio.ItemPtr) bool { - if itemName, ok := o.keyIO.Names[ptr]; ok && bytes.Equal(itemName, name) { - wants.InsertFrom(o.rebuilt.Tree(ctx, treeID).LeafToRoots(ctx, ptr.Node)) - } - return true - }) - o.wantAugment(ctx, wantKey, wants) -} - -func (o *rebuilder) _walkRange( - ctx context.Context, - items *containers.SortedMap[btrfsprim.Key, keyio.ItemPtr], - treeID, objID btrfsprim.ObjID, typ btrfsprim.ItemType, - beg, end uint64, - fn func(key btrfsprim.Key, ptr keyio.ItemPtr, beg, end uint64), -) { - min := btrfsprim.Key{ - ObjectID: objID, - ItemType: typ, - Offset: 0, // *NOT* `beg` - } - max := btrfsprim.Key{ - ObjectID: objID, - ItemType: typ, - Offset: end - 1, - } - items.Subrange( - func(runKey btrfsprim.Key, _ keyio.ItemPtr) int { - switch { - case min.Compare(runKey) < 0: - return 1 - case max.Compare(runKey) > 0: - return -1 - default: - return 0 - } - }, - func(runKey btrfsprim.Key, runPtr keyio.ItemPtr) bool { - runSizeAndErr, ok := o.keyIO.Sizes[runPtr] - if !ok { - panic(fmt.Errorf("should not happen: %v (%v) did not have a size recorded", - runPtr, keyAndTree{TreeID: treeID, Key: runKey})) - } - if runSizeAndErr.Err != nil { - o.fsErr(ctx, fmt.Errorf("get size: %v (%v): %w", - runPtr, keyAndTree{TreeID: treeID, Key: runKey}, - runSizeAndErr.Err)) - return true - } - runSize := runSizeAndErr.Size - if runSize == 0 { - return true - } - runBeg := runKey.Offset - runEnd := runBeg + runSize - if runEnd <= beg { - return true - } - - fn(runKey, runPtr, runBeg, runEnd) - return true - }) -} - -type gap struct { - // range is [Beg,End) - Beg, End uint64 -} - -// Compare implements containers.Ordered. -func (a gap) Compare(b gap) int { - return containers.NativeCompare(a.Beg, b.Beg) -} - -func (o *rebuilder) _wantRange( - ctx context.Context, reason string, - treeID btrfsprim.ObjID, objID btrfsprim.ObjID, typ btrfsprim.ItemType, - beg, end uint64, -) { - wantKey := WantWithTree{ - TreeID: treeID, - Key: Want{ - ObjectID: objID, - ItemType: typ, - OffsetType: offsetAny, - }, - } - ctx = withWant(ctx, logFieldItemWant, reason, wantKey) - wantKey.Key.OffsetType = offsetRange - - if o.rebuilt.Tree(ctx, treeID) == nil { - o.enqueueRetry(treeID) - return - } - - // Step 1: Build a listing of the gaps. - // - // Start with a gap of the whole range, then subtract each run - // from it. - gaps := new(containers.RBTree[gap]) - gaps.Insert(gap{ - Beg: beg, - End: end, - }) - o._walkRange( - ctx, - o.rebuilt.Tree(ctx, treeID).Items(ctx), - treeID, objID, typ, beg, end, - func(runKey btrfsprim.Key, _ keyio.ItemPtr, runBeg, runEnd uint64) { - var overlappingGaps []*containers.RBNode[gap] - gaps.Subrange( - func(gap gap) int { - switch { - case gap.End <= runBeg: - return 1 - case runEnd <= gap.Beg: - return -1 - default: - return 0 - } - }, - func(node *containers.RBNode[gap]) bool { - overlappingGaps = append(overlappingGaps, node) - return true - }) - if len(overlappingGaps) == 0 { - return - } - gapsBeg := overlappingGaps[0].Value.Beg - gapsEnd := overlappingGaps[len(overlappingGaps)-1].Value.End - for _, gap := range overlappingGaps { - gaps.Delete(gap) - } - if gapsBeg < runBeg { - gaps.Insert(gap{ - Beg: gapsBeg, - End: runBeg, - }) - } - if gapsEnd > runEnd { - gaps.Insert(gap{ - Beg: runEnd, - End: gapsEnd, - }) - } - }) - - // Step 2: Fill each gap. - if gaps.Len() == 0 { - return - } - potentialItems := o.rebuilt.Tree(ctx, treeID).PotentialItems(ctx) - gaps.Range(func(rbNode *containers.RBNode[gap]) bool { - gap := rbNode.Value - last := gap.Beg - o._walkRange( - ctx, - potentialItems, - treeID, objID, typ, gap.Beg, gap.End, - func(k btrfsprim.Key, v keyio.ItemPtr, runBeg, runEnd uint64) { - // TODO: This is dumb and greedy. - if last < runBeg { - // log an error - wantKey.Key.OffsetLow = last - wantKey.Key.OffsetHigh = runBeg - wantCtx := withWant(ctx, logFieldItemWant, reason, wantKey) - o.wantAugment(wantCtx, wantKey, nil) - } - wantKey.Key.OffsetLow = gap.Beg - wantKey.Key.OffsetHigh = gap.End - wantCtx := withWant(ctx, logFieldItemWant, reason, wantKey) - o.wantAugment(wantCtx, wantKey, o.rebuilt.Tree(wantCtx, treeID).LeafToRoots(wantCtx, v.Node)) - last = runEnd - }) - if last < gap.End { - // log an error - wantKey.Key.OffsetLow = last - wantKey.Key.OffsetHigh = gap.End - wantCtx := withWant(ctx, logFieldItemWant, reason, wantKey) - o.wantAugment(wantCtx, wantKey, nil) - } - return true - }) -} - -// func implements rebuildCallbacks. -// -// interval is [beg, end) -func (o *rebuilder) wantCSum(ctx context.Context, reason string, inodeTree, inode btrfsprim.ObjID, beg, end btrfsvol.LogicalAddr) { - inodeWant := WantWithTree{ - TreeID: inodeTree, - Key: Want{ - ObjectID: inode, - ItemType: btrfsitem.INODE_ITEM_KEY, - OffsetType: offsetExact, - OffsetLow: 0, - }, - } - inodeCtx := withWant(ctx, logFieldItemWant, reason, inodeWant) - if !o._wantOff(inodeCtx, inodeWant) { - o.enqueueRetry(inodeTree) - return - } - inodePtr, ok := o.rebuilt.Tree(inodeCtx, inodeTree).Items(inodeCtx).Load(inodeWant.Key.Key()) - if !ok { - panic(fmt.Errorf("should not happen: could not load key: %v", inodeWant)) - } - inodeFlags, ok := o.keyIO.Flags[inodePtr] - if !ok { - panic(fmt.Errorf("should not happen: INODE_ITEM did not have flags recorded")) - } - if inodeFlags.Err != nil { - o.fsErr(inodeCtx, inodeFlags.Err) - return - } - - if inodeFlags.NoDataSum { - return - } - - o._wantRange( - ctx, reason, - btrfsprim.CSUM_TREE_OBJECTID, btrfsprim.EXTENT_CSUM_OBJECTID, btrfsprim.EXTENT_CSUM_KEY, - uint64(roundDown(beg, btrfssum.BlockSize)), uint64(roundUp(end, btrfssum.BlockSize))) -} - -// wantFileExt implements rebuildCallbacks. -func (o *rebuilder) wantFileExt(ctx context.Context, reason string, treeID btrfsprim.ObjID, ino btrfsprim.ObjID, size int64) { - o._wantRange( - ctx, reason, - treeID, ino, btrfsprim.EXTENT_DATA_KEY, - 0, uint64(size)) -} |