From b97b6962d5027ae3db2bb03db1e5303702c3e9b2 Mon Sep 17 00:00:00 2001 From: Luke Shumaker Date: Thu, 2 Mar 2023 16:02:42 -0700 Subject: btrfsutil: OldRebuiltForrest: Drop skinny paths This changes errors to not have a Path attached to them, only tracking their spans; and it changes the Paths from TreeWalk to only have the leaf node. --- lib/btrfsutil/old_rebuilt_forrest.go | 137 ++++++++++++++++++++++---------- lib/btrfsutil/skinny_paths.go | 146 ----------------------------------- 2 files changed, 97 insertions(+), 186 deletions(-) delete mode 100644 lib/btrfsutil/skinny_paths.go diff --git a/lib/btrfsutil/old_rebuilt_forrest.go b/lib/btrfsutil/old_rebuilt_forrest.go index 6705535..8bc02df 100644 --- a/lib/btrfsutil/old_rebuilt_forrest.go +++ b/lib/btrfsutil/old_rebuilt_forrest.go @@ -40,9 +40,20 @@ func (e oldRebuiltTreeError) Unwrap() error { } type oldRebuiltTreeValue struct { - Path SkinnyPath Key btrfsprim.Key ItemSize uint32 + + Node nodeInfo + Slot int +} + +type nodeInfo struct { + LAddr btrfsvol.LogicalAddr + Level uint8 + Generation btrfsprim.Generation + Owner btrfsprim.ObjID + MinItem btrfsprim.Key + MaxItem btrfsprim.Key } // Compare implements containers.Ordered. @@ -68,8 +79,6 @@ type OldRebuiltForrest struct { ctx context.Context //nolint:containedctx // don't have an option while keeping the same API inner *btrfs.FS - arena *SkinnyPathArena - // btrfsprim.ROOT_TREE_OBJECTID rootTreeMu sync.Mutex rootTree *oldRebuiltTree @@ -133,16 +142,7 @@ func (bt *OldRebuiltForrest) RebuiltTree(treeID btrfsprim.ObjID) oldRebuiltTree treeRoot, err = btrfstree.LookupTreeRoot(bt, *sb, treeID) } } - if bt.arena == nil { - var _sb btrfstree.Superblock - if sb != nil { - _sb = *sb - } - bt.arena = &SkinnyPathArena{ - FS: bt.inner, - SB: _sb, - } - } + cacheEntry := newOldRebuiltTree() if err != nil { cacheEntry.RootErr = err @@ -151,6 +151,7 @@ func (bt *OldRebuiltForrest) RebuiltTree(treeID btrfsprim.ObjID) oldRebuiltTree bt.rawTreeWalk(*treeRoot, cacheEntry, nil) dlog.Infof(bt.ctx, "... done indexing tree %v", treeID) } + if treeID == btrfsprim.ROOT_TREE_OBJECTID { bt.rootTree = &cacheEntry } else { @@ -159,6 +160,8 @@ func (bt *OldRebuiltForrest) RebuiltTree(treeID btrfsprim.ObjID) oldRebuiltTree return cacheEntry } +func discardOK[T any](x T, _ bool) T { return x } + func (bt *OldRebuiltForrest) rawTreeWalk(root btrfstree.TreeRoot, cacheEntry oldRebuiltTree, walked *[]btrfsprim.Key) { errHandle := func(err *btrfstree.TreeError) { if len(err.Path) > 0 && err.Path.Node(-1).ToNodeAddr == 0 { @@ -173,7 +176,32 @@ func (bt *OldRebuiltForrest) rawTreeWalk(root btrfstree.TreeRoot, cacheEntry old }) } + var curNode nodeInfo cbs := btrfstree.TreeWalkHandler{ + BadNode: func(path btrfstree.TreePath, node *btrfstree.Node, err error) error { + if node != nil { + curNode = nodeInfo{ + LAddr: path.Node(-1).ToNodeAddr, + Level: node.Head.Level, + Generation: node.Head.Generation, + Owner: node.Head.Owner, + MinItem: discardOK(node.MinItem()), + MaxItem: discardOK(node.MaxItem()), + } + } + return err + }, + Node: func(path btrfstree.TreePath, node *btrfstree.Node) error { + curNode = nodeInfo{ + LAddr: path.Node(-1).ToNodeAddr, + Level: node.Head.Level, + Generation: node.Head.Generation, + Owner: node.Head.Owner, + MinItem: discardOK(node.MinItem()), + MaxItem: discardOK(node.MaxItem()), + } + return nil + }, Item: func(path btrfstree.TreePath, item btrfstree.Item) error { if cacheEntry.Items.Search(func(v oldRebuiltTreeValue) int { return item.Key.Compare(v.Key) }) != nil { // This is a panic because I'm not really sure what the best way to @@ -182,9 +210,11 @@ func (bt *OldRebuiltForrest) rawTreeWalk(root btrfstree.TreeRoot, cacheEntry old panic(fmt.Errorf("dup key=%v in tree=%v", item.Key, root.TreeID)) } cacheEntry.Items.Insert(oldRebuiltTreeValue{ - Path: bt.arena.Deflate(path), Key: item.Key, ItemSize: item.BodySize, + + Node: curNode, + Slot: path.Node(-1).FromItemSlot, }) if walked != nil { *walked = append(*walked, item.Key) @@ -217,6 +247,33 @@ func (tree oldRebuiltTree) addErrs(fn func(btrfsprim.Key, uint32) int, err error return errs } +func (bt *OldRebuiltForrest) readNode(nodeInfo nodeInfo) *btrfstree.Node { + sb, err := bt.inner.Superblock() + if err != nil { + panic(fmt.Errorf("should not happen: i/o error: %w", err)) + } + + node, err := btrfstree.ReadNode[btrfsvol.LogicalAddr](bt.inner, *sb, nodeInfo.LAddr, btrfstree.NodeExpectations{ + LAddr: containers.Optional[btrfsvol.LogicalAddr]{OK: true, Val: nodeInfo.LAddr}, + Level: containers.Optional[uint8]{OK: true, Val: nodeInfo.Level}, + Generation: containers.Optional[btrfsprim.Generation]{OK: true, Val: nodeInfo.Generation}, + Owner: func(treeID btrfsprim.ObjID) error { + if treeID != nodeInfo.Owner { + return fmt.Errorf("expected owner=%v but claims to have owner=%v", + nodeInfo.Owner, treeID) + } + return nil + }, + MinItem: containers.Optional[btrfsprim.Key]{OK: true, Val: nodeInfo.MinItem}, + MaxItem: containers.Optional[btrfsprim.Key]{OK: true, Val: nodeInfo.MaxItem}, + }) + if err != nil { + panic(fmt.Errorf("should not happen: i/o error: %w", err)) + } + + return node +} + func (bt *OldRebuiltForrest) TreeSearch(treeID btrfsprim.ObjID, searcher btrfstree.TreeSearcher) (btrfstree.Item, error) { tree := bt.RebuiltTree(treeID) if tree.RootErr != nil { @@ -230,14 +287,10 @@ func (bt *OldRebuiltForrest) TreeSearch(treeID btrfsprim.ObjID, searcher btrfstr return btrfstree.Item{}, fmt.Errorf("item with %s: %w", searcher, tree.addErrs(searcher.Search, btrfstree.ErrNoItem)) } - itemPath := bt.arena.Inflate(indexItem.Value.Path) - node, err := bt.inner.ReadNode(itemPath.Parent()) + node := bt.readNode(indexItem.Value.Node) defer node.Free() - if err != nil { - return btrfstree.Item{}, fmt.Errorf("item with %s: %w", searcher, tree.addErrs(searcher.Search, err)) - } - item := node.BodyLeaf[itemPath.Node(-1).FromItemSlot] + item := node.BodyLeaf[indexItem.Value.Slot] item.Body = item.Body.CloneItem() // Since we were only asked to return 1 item, it isn't @@ -266,18 +319,12 @@ func (bt *OldRebuiltForrest) TreeSearchAll(treeID btrfsprim.ObjID, searcher btrf ret := make([]btrfstree.Item, len(indexItems)) var node *btrfstree.Node - for i := range indexItems { - itemPath := bt.arena.Inflate(indexItems[i].Path) - if node == nil || node.Head.Addr != itemPath.Node(-2).ToNodeAddr { - var err error + for i, indexItem := range indexItems { + if node == nil || node.Head.Addr != indexItem.Node.LAddr { node.Free() - node, err = bt.inner.ReadNode(itemPath.Parent()) - if err != nil { - node.Free() - return nil, fmt.Errorf("items with %s: %w", searcher, tree.addErrs(searcher.Search, err)) - } + node = bt.readNode(indexItem.Node) } - ret[i] = node.BodyLeaf[itemPath.Node(-1).FromItemSlot] + ret[i] = node.BodyLeaf[indexItem.Slot] ret[i].Body = ret[i].Body.CloneItem() } node.Free() @@ -312,18 +359,28 @@ func (bt *OldRebuiltForrest) TreeWalk(ctx context.Context, treeID btrfsprim.ObjI if bt.ctx.Err() != nil { return false } - itemPath := bt.arena.Inflate(indexItem.Value.Path) - if node == nil || node.Head.Addr != itemPath.Node(-2).ToNodeAddr { - var err error + if node == nil || node.Head.Addr != indexItem.Value.Node.LAddr { node.Free() - node, err = bt.inner.ReadNode(itemPath.Parent()) - if err != nil { - node.Free() - errHandle(&btrfstree.TreeError{Path: itemPath, Err: err}) - return true - } + node = bt.readNode(indexItem.Value.Node) + } + item := node.BodyLeaf[indexItem.Value.Slot] + + itemPath := btrfstree.TreePath{ + { + FromTree: treeID, + ToNodeAddr: indexItem.Value.Node.LAddr, + ToNodeGeneration: indexItem.Value.Node.Generation, + ToNodeLevel: indexItem.Value.Node.Level, + ToKey: indexItem.Value.Node.MinItem, + ToMaxKey: indexItem.Value.Node.MaxItem, + }, + { + FromTree: indexItem.Value.Node.Owner, + FromItemSlot: indexItem.Value.Slot, + ToKey: indexItem.Value.Key, + ToMaxKey: indexItem.Value.Key, + }, } - item := node.BodyLeaf[itemPath.Node(-1).FromItemSlot] if err := cbs.Item(itemPath, item); err != nil { errHandle(&btrfstree.TreeError{Path: itemPath, Err: err}) } diff --git a/lib/btrfsutil/skinny_paths.go b/lib/btrfsutil/skinny_paths.go deleted file mode 100644 index 1361fff..0000000 --- a/lib/btrfsutil/skinny_paths.go +++ /dev/null @@ -1,146 +0,0 @@ -// Copyright (C) 2022-2023 Luke Shumaker -// -// SPDX-License-Identifier: GPL-2.0-or-later - -package btrfsutil - -import ( - "fmt" - - "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/diskio" - "git.lukeshu.com/btrfs-progs-ng/lib/textui" -) - -type skinnyItem struct { - Node btrfsvol.LogicalAddr - Item int -} - -type SkinnyPath struct { - Root btrfsvol.LogicalAddr - Items []int -} - -type SkinnyPathArena struct { - FS diskio.File[btrfsvol.LogicalAddr] - SB btrfstree.Superblock - - fatRoots map[btrfsvol.LogicalAddr]btrfstree.TreePathElem - fatItems containers.ARCache[skinnyItem, btrfstree.TreePathElem] -} - -func (a *SkinnyPathArena) init() { - if a.fatRoots == nil { - a.fatRoots = make(map[btrfsvol.LogicalAddr]btrfstree.TreePathElem) - a.fatItems.MaxLen = textui.Tunable(128 * 1024) - } -} - -func (a *SkinnyPathArena) getItem(parent btrfstree.TreePath, itemSlot int) (btrfstree.TreePathElem, error) { - if itemSlot < 0 { - panic("should not happen") - } - - a.init() - - ret, ok := a.fatItems.Load(skinnyItem{ - Node: parent.Node(-1).ToNodeAddr, - Item: itemSlot, - }) - if ok { - return ret, nil - } - - node, err := btrfstree.ReadNode[btrfsvol.LogicalAddr](a.FS, a.SB, parent.Node(-1).ToNodeAddr, btrfstree.NodeExpectations{}) - defer node.Free() - if err != nil { - return btrfstree.TreePathElem{}, err - } - if node.Head.Level > 0 { - if itemSlot >= len(node.BodyInterior) { - panic("should not happen") - } - for i, item := range node.BodyInterior { - toMaxKey := parent.Node(-1).ToMaxKey - if i+1 < len(node.BodyInterior) { - toMaxKey = node.BodyInterior[i+1].Key.Mm() - } - elem := btrfstree.TreePathElem{ - FromTree: node.Head.Owner, - FromItemSlot: i, - ToNodeAddr: item.BlockPtr, - ToNodeGeneration: item.Generation, - ToNodeLevel: node.Head.Level - 1, - ToKey: item.Key, - ToMaxKey: toMaxKey, - } - a.fatItems.Store(skinnyItem{Node: parent.Node(-1).ToNodeAddr, Item: i}, elem) - if i == itemSlot { - ret = elem - } - } - } else { - if itemSlot >= len(node.BodyLeaf) { - panic("should not happen") - } - for i, item := range node.BodyLeaf { - elem := btrfstree.TreePathElem{ - FromTree: node.Head.Owner, - FromItemSlot: i, - ToKey: item.Key, - ToMaxKey: item.Key, - } - a.fatItems.Store(skinnyItem{Node: parent.Node(-1).ToNodeAddr, Item: i}, elem) - if i == itemSlot { - ret = elem - } - } - } - - return ret, nil -} - -func (a *SkinnyPathArena) Deflate(fat btrfstree.TreePath) SkinnyPath { - a.init() - - var ret SkinnyPath - - var prevNode btrfsvol.LogicalAddr - for i, elem := range fat { - if i == 0 { - a.fatRoots[elem.ToNodeAddr] = elem - ret.Root = elem.ToNodeAddr - } else { - a.fatItems.Store(skinnyItem{Node: prevNode, Item: elem.FromItemSlot}, elem) - ret.Items = append(ret.Items, elem.FromItemSlot) - } - prevNode = elem.ToNodeAddr - } - return ret -} - -func (a *SkinnyPathArena) Inflate(skinny SkinnyPath) btrfstree.TreePath { - a.init() - - ret := make(btrfstree.TreePath, 0, 1+len(skinny.Items)) - - root, ok := a.fatRoots[skinny.Root] - if !ok { - panic(fmt.Errorf("SkinnyPathArena.Inflate: no stored TreePathElem for root->%v", - skinny.Root)) - } - ret = append(ret, root) - - for _, itemSlot := range skinny.Items { - elem, err := a.getItem(ret, itemSlot) - if err != nil { - panic(err) - } - ret = append(ret, elem) - } - - return ret -} -- cgit v1.1-4-g5e80