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.

2 files changed, 97 insertions, 186 deletions

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 <lukeshu@lukeshu.com>
-//
-// 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
-}