From 1bc243ca607c22e232017b0f1b4badcde288a9b3 Mon Sep 17 00:00:00 2001
From: Luke Shumaker <lukeshu@lukeshu.com>
Date: Thu, 16 Mar 2023 09:17:35 -0600
Subject: btrfstree: Have ReadNode return a *Node rather than a
 *diskio.Ref[Addr, Node]

... and take a ReaderAt instead of a diskio.File.
---
 lib/btrfsutil/old_rebuilt_forrest.go | 37 ++++++++++++++++++------------------
 1 file changed, 18 insertions(+), 19 deletions(-)

(limited to 'lib/btrfsutil/old_rebuilt_forrest.go')

diff --git a/lib/btrfsutil/old_rebuilt_forrest.go b/lib/btrfsutil/old_rebuilt_forrest.go
index d49f34e..2ec1d83 100644
--- a/lib/btrfsutil/old_rebuilt_forrest.go
+++ b/lib/btrfsutil/old_rebuilt_forrest.go
@@ -17,7 +17,6 @@ import (
 	"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"
 )
 
 type oldRebuiltTree struct {
@@ -226,12 +225,12 @@ func (bt *OldRebuiltForrest) TreeSearch(treeID btrfsprim.ObjID, searcher btrfstr
 
 	itemPath := bt.arena.Inflate(indexItem.Value.Path)
 	node, err := bt.inner.ReadNode(itemPath.Parent())
-	defer btrfstree.FreeNodeRef(node)
+	defer node.Free()
 	if err != nil {
 		return btrfstree.Item{}, fmt.Errorf("item with %s: %w", searcher, bt.addErrs(tree, searcher.Search, err))
 	}
 
-	item := node.Data.BodyLeaf[itemPath.Node(-1).FromItemSlot]
+	item := node.BodyLeaf[itemPath.Node(-1).FromItemSlot]
 	item.Body = item.Body.CloneItem()
 
 	// Since we were only asked to return 1 item, it isn't
@@ -259,22 +258,22 @@ func (bt *OldRebuiltForrest) TreeSearchAll(treeID btrfsprim.ObjID, searcher btrf
 	}
 
 	ret := make([]btrfstree.Item, len(indexItems))
-	var node *diskio.Ref[btrfsvol.LogicalAddr, btrfstree.Node]
+	var node *btrfstree.Node
 	for i := range indexItems {
 		itemPath := bt.arena.Inflate(indexItems[i].Path)
-		if node == nil || node.Addr != itemPath.Node(-2).ToNodeAddr {
+		if node == nil || node.Head.Addr != itemPath.Node(-2).ToNodeAddr {
 			var err error
-			btrfstree.FreeNodeRef(node)
+			node.Free()
 			node, err = bt.inner.ReadNode(itemPath.Parent())
 			if err != nil {
-				btrfstree.FreeNodeRef(node)
+				node.Free()
 				return nil, fmt.Errorf("items with %s: %w", searcher, bt.addErrs(tree, searcher.Search, err))
 			}
 		}
-		ret[i] = node.Data.BodyLeaf[itemPath.Node(-1).FromItemSlot]
+		ret[i] = node.BodyLeaf[itemPath.Node(-1).FromItemSlot]
 		ret[i].Body = ret[i].Body.CloneItem()
 	}
-	btrfstree.FreeNodeRef(node)
+	node.Free()
 
 	err := bt.addErrs(tree, searcher.Search, nil)
 	if err != nil {
@@ -298,7 +297,7 @@ func (bt *OldRebuiltForrest) TreeWalk(ctx context.Context, treeID btrfsprim.ObjI
 	if cbs.Item == nil {
 		return
 	}
-	var node *diskio.Ref[btrfsvol.LogicalAddr, btrfstree.Node]
+	var node *btrfstree.Node
 	tree.Items.Range(func(indexItem *containers.RBNode[oldRebuiltTreeValue]) bool {
 		if ctx.Err() != nil {
 			return false
@@ -307,23 +306,23 @@ func (bt *OldRebuiltForrest) TreeWalk(ctx context.Context, treeID btrfsprim.ObjI
 			return false
 		}
 		itemPath := bt.arena.Inflate(indexItem.Value.Path)
-		if node == nil || node.Addr != itemPath.Node(-2).ToNodeAddr {
+		if node == nil || node.Head.Addr != itemPath.Node(-2).ToNodeAddr {
 			var err error
-			btrfstree.FreeNodeRef(node)
+			node.Free()
 			node, err = bt.inner.ReadNode(itemPath.Parent())
 			if err != nil {
-				btrfstree.FreeNodeRef(node)
+				node.Free()
 				errHandle(&btrfstree.TreeError{Path: itemPath, Err: err})
 				return true
 			}
 		}
-		item := node.Data.BodyLeaf[itemPath.Node(-1).FromItemSlot]
+		item := node.BodyLeaf[itemPath.Node(-1).FromItemSlot]
 		if err := cbs.Item(itemPath, item); err != nil {
 			errHandle(&btrfstree.TreeError{Path: itemPath, Err: err})
 		}
 		return true
 	})
-	btrfstree.FreeNodeRef(node)
+	node.Free()
 }
 
 func (bt *OldRebuiltForrest) Superblock() (*btrfstree.Superblock, error) {
@@ -343,8 +342,8 @@ func (bt *OldRebuiltForrest) Augment(treeID btrfsprim.ObjID, nodeAddr btrfsvol.L
 	if tree.RootErr != nil {
 		return nil, tree.RootErr
 	}
-	nodeRef, err := btrfstree.ReadNode[btrfsvol.LogicalAddr](bt.inner, *sb, nodeAddr, btrfstree.NodeExpectations{})
-	defer btrfstree.FreeNodeRef(nodeRef)
+	node, err := btrfstree.ReadNode[btrfsvol.LogicalAddr](bt.inner, *sb, nodeAddr, btrfstree.NodeExpectations{})
+	defer node.Free()
 	if err != nil {
 		return nil, err
 	}
@@ -352,8 +351,8 @@ func (bt *OldRebuiltForrest) Augment(treeID btrfsprim.ObjID, nodeAddr btrfsvol.L
 	bt.rawTreeWalk(btrfstree.TreeRoot{
 		TreeID:     treeID,
 		RootNode:   nodeAddr,
-		Level:      nodeRef.Data.Head.Level,
-		Generation: nodeRef.Data.Head.Generation,
+		Level:      node.Head.Level,
+		Generation: node.Head.Generation,
 	}, tree, &ret)
 	return ret, nil
 }
-- 
cgit v1.2.3-54-g00ecf


From 8b5aa5b60839b39f75257ee1c2bafa59459a80e6 Mon Sep 17 00:00:00 2001
From: Luke Shumaker <lukeshu@lukeshu.com>
Date: Fri, 17 Mar 2023 22:20:10 -0400
Subject: btrfsutil: OldRebuiltForrest: Don't use Paths when tracking errors

---
 lib/btrfsutil/old_rebuilt_forrest.go | 33 ++++++++++++++++++++-------------
 1 file changed, 20 insertions(+), 13 deletions(-)

(limited to 'lib/btrfsutil/old_rebuilt_forrest.go')

diff --git a/lib/btrfsutil/old_rebuilt_forrest.go b/lib/btrfsutil/old_rebuilt_forrest.go
index 2ec1d83..a6c2661 100644
--- a/lib/btrfsutil/old_rebuilt_forrest.go
+++ b/lib/btrfsutil/old_rebuilt_forrest.go
@@ -26,8 +26,17 @@ type oldRebuiltTree struct {
 }
 
 type oldRebuiltTreeError struct {
-	Path SkinnyPath
-	Err  error
+	Min btrfsprim.Key
+	Max btrfsprim.Key
+	Err error
+}
+
+func (e oldRebuiltTreeError) Error() string {
+	return fmt.Sprintf("keys %v-%v: %v", e.Min, e.Max, e.Err)
+}
+
+func (e oldRebuiltTreeError) Unwrap() error {
+	return e.Err
 }
 
 type oldRebuiltTreeValue struct {
@@ -41,15 +50,15 @@ func (a oldRebuiltTreeValue) Compare(b oldRebuiltTreeValue) int {
 	return a.Key.Compare(b.Key)
 }
 
-func newOldRebuiltTree(arena *SkinnyPathArena) oldRebuiltTree {
+func newOldRebuiltTree() oldRebuiltTree {
 	return oldRebuiltTree{
 		Items: new(containers.RBTree[oldRebuiltTreeValue]),
 		Errors: &containers.IntervalTree[btrfsprim.Key, oldRebuiltTreeError]{
 			MinFn: func(err oldRebuiltTreeError) btrfsprim.Key {
-				return arena.Inflate(err.Path).Node(-1).ToKey
+				return err.Min
 			},
 			MaxFn: func(err oldRebuiltTreeError) btrfsprim.Key {
-				return arena.Inflate(err.Path).Node(-1).ToMaxKey
+				return err.Max
 			},
 		},
 	}
@@ -134,7 +143,7 @@ func (bt *OldRebuiltForrest) RebuiltTree(treeID btrfsprim.ObjID) oldRebuiltTree
 			SB: _sb,
 		}
 	}
-	cacheEntry := newOldRebuiltTree(bt.arena)
+	cacheEntry := newOldRebuiltTree()
 	if err != nil {
 		cacheEntry.RootErr = err
 	} else {
@@ -158,8 +167,9 @@ func (bt *OldRebuiltForrest) rawTreeWalk(root btrfstree.TreeRoot, cacheEntry old
 			panic(fmt.Errorf("TODO: error parsing item: %w", err))
 		}
 		cacheEntry.Errors.Insert(oldRebuiltTreeError{
-			Path: bt.arena.Deflate(err.Path),
-			Err:  err.Err,
+			Min: err.Path.Node(-1).ToKey,
+			Max: err.Path.Node(-1).ToMaxKey,
+			Err: err.Err,
 		})
 	}
 
@@ -190,15 +200,12 @@ func (bt *OldRebuiltForrest) TreeLookup(treeID btrfsprim.ObjID, key btrfsprim.Ke
 	return bt.TreeSearch(treeID, btrfstree.SearchExactKey(key))
 }
 
-func (bt *OldRebuiltForrest) addErrs(tree oldRebuiltTree, fn func(btrfsprim.Key, uint32) int, err error) error {
+func (*OldRebuiltForrest) addErrs(tree oldRebuiltTree, fn func(btrfsprim.Key, uint32) int, err error) error {
 	var errs derror.MultiError
 	tree.Errors.Subrange(
 		func(k btrfsprim.Key) int { return fn(k, 0) },
 		func(v oldRebuiltTreeError) bool {
-			path := bt.arena.Inflate(v.Path)
-			minKey := path.Node(-1).ToKey
-			maxKey := path.Node(-1).ToMaxKey
-			errs = append(errs, fmt.Errorf("keys %v-%v: %w", minKey, maxKey, v.Err))
+			errs = append(errs, v)
 			return true
 		})
 	if len(errs) == 0 {
-- 
cgit v1.2.3-54-g00ecf


From 95e542df75675389a3598150be9c85c4834bbb98 Mon Sep 17 00:00:00 2001
From: Luke Shumaker <lukeshu@lukeshu.com>
Date: Fri, 17 Mar 2023 22:26:42 -0400
Subject: btrfsutil: OldRebuiltForrest: Move .addErrs() from the forrest to the
 tree

---
 lib/btrfsutil/old_rebuilt_forrest.go | 14 +++++++-------
 1 file changed, 7 insertions(+), 7 deletions(-)

(limited to 'lib/btrfsutil/old_rebuilt_forrest.go')

diff --git a/lib/btrfsutil/old_rebuilt_forrest.go b/lib/btrfsutil/old_rebuilt_forrest.go
index a6c2661..6705535 100644
--- a/lib/btrfsutil/old_rebuilt_forrest.go
+++ b/lib/btrfsutil/old_rebuilt_forrest.go
@@ -200,7 +200,7 @@ func (bt *OldRebuiltForrest) TreeLookup(treeID btrfsprim.ObjID, key btrfsprim.Ke
 	return bt.TreeSearch(treeID, btrfstree.SearchExactKey(key))
 }
 
-func (*OldRebuiltForrest) addErrs(tree oldRebuiltTree, fn func(btrfsprim.Key, uint32) int, err error) error {
+func (tree oldRebuiltTree) addErrs(fn func(btrfsprim.Key, uint32) int, err error) error {
 	var errs derror.MultiError
 	tree.Errors.Subrange(
 		func(k btrfsprim.Key) int { return fn(k, 0) },
@@ -227,21 +227,21 @@ func (bt *OldRebuiltForrest) TreeSearch(treeID btrfsprim.ObjID, searcher btrfstr
 		return searcher.Search(indexItem.Key, indexItem.ItemSize)
 	})
 	if indexItem == nil {
-		return btrfstree.Item{}, fmt.Errorf("item with %s: %w", searcher, bt.addErrs(tree, searcher.Search, btrfstree.ErrNoItem))
+		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())
 	defer node.Free()
 	if err != nil {
-		return btrfstree.Item{}, fmt.Errorf("item with %s: %w", searcher, bt.addErrs(tree, searcher.Search, err))
+		return btrfstree.Item{}, fmt.Errorf("item with %s: %w", searcher, tree.addErrs(searcher.Search, err))
 	}
 
 	item := node.BodyLeaf[itemPath.Node(-1).FromItemSlot]
 	item.Body = item.Body.CloneItem()
 
 	// Since we were only asked to return 1 item, it isn't
-	// necessary to augment this `nil` with bt.addErrs().
+	// necessary to augment this `nil` with tree.addErrs().
 	return item, nil
 }
 
@@ -261,7 +261,7 @@ func (bt *OldRebuiltForrest) TreeSearchAll(treeID btrfsprim.ObjID, searcher btrf
 			return true
 		})
 	if len(indexItems) == 0 {
-		return nil, fmt.Errorf("items with %s: %w", searcher, bt.addErrs(tree, searcher.Search, btrfstree.ErrNoItem))
+		return nil, fmt.Errorf("items with %s: %w", searcher, tree.addErrs(searcher.Search, btrfstree.ErrNoItem))
 	}
 
 	ret := make([]btrfstree.Item, len(indexItems))
@@ -274,7 +274,7 @@ func (bt *OldRebuiltForrest) TreeSearchAll(treeID btrfsprim.ObjID, searcher btrf
 			node, err = bt.inner.ReadNode(itemPath.Parent())
 			if err != nil {
 				node.Free()
-				return nil, fmt.Errorf("items with %s: %w", searcher, bt.addErrs(tree, searcher.Search, err))
+				return nil, fmt.Errorf("items with %s: %w", searcher, tree.addErrs(searcher.Search, err))
 			}
 		}
 		ret[i] = node.BodyLeaf[itemPath.Node(-1).FromItemSlot]
@@ -282,7 +282,7 @@ func (bt *OldRebuiltForrest) TreeSearchAll(treeID btrfsprim.ObjID, searcher btrf
 	}
 	node.Free()
 
-	err := bt.addErrs(tree, searcher.Search, nil)
+	err := tree.addErrs(searcher.Search, nil)
 	if err != nil {
 		err = fmt.Errorf("items with %s: %w", searcher, err)
 	}
-- 
cgit v1.2.3-54-g00ecf


From b97b6962d5027ae3db2bb03db1e5303702c3e9b2 Mon Sep 17 00:00:00 2001
From: Luke Shumaker <lukeshu@lukeshu.com>
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

(limited to 'lib/btrfsutil/old_rebuilt_forrest.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 <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
-}
-- 
cgit v1.2.3-54-g00ecf


From 17e5d1366a77bbe0e8d32b7bf16829a4f855e854 Mon Sep 17 00:00:00 2001
From: Luke Shumaker <lukeshu@lukeshu.com>
Date: Fri, 10 Mar 2023 15:22:07 -0700
Subject: tree-wide: s/TreePath/Path/g

btrfstree.TreePath stutters.
---
 cmd/btrfs-rec/inspect/dumptrees/print_tree.go |  8 +++----
 cmd/btrfs-rec/inspect_lstrees.go              |  6 ++---
 cmd/btrfs-rec/inspect_spewitems.go            |  4 ++--
 lib/btrfs/btrfstree/btree.go                  | 20 ++++++++---------
 lib/btrfs/btrfstree/btree_tree.go             | 32 +++++++++++++--------------
 lib/btrfs/btrfstree/path.go                   | 22 +++++++++---------
 lib/btrfs/btrfstree/readnode.go               |  2 +-
 lib/btrfs/io2_lv.go                           |  2 +-
 lib/btrfs/io3_btree.go                        |  4 ++--
 lib/btrfsutil/old_rebuilt_forrest.go          | 10 ++++-----
 lib/btrfsutil/rebuilt_forrest.go              |  2 +-
 lib/btrfsutil/walk.go                         |  4 ++--
 12 files changed, 58 insertions(+), 58 deletions(-)

(limited to 'lib/btrfsutil/old_rebuilt_forrest.go')

diff --git a/cmd/btrfs-rec/inspect/dumptrees/print_tree.go b/cmd/btrfs-rec/inspect/dumptrees/print_tree.go
index 9572f3a..60303e9 100644
--- a/cmd/btrfs-rec/inspect/dumptrees/print_tree.go
+++ b/cmd/btrfs-rec/inspect/dumptrees/print_tree.go
@@ -53,7 +53,7 @@ func DumpTrees(ctx context.Context, out io.Writer, fs *btrfs.FS) {
 			dlog.Error(ctx, err)
 		},
 		btrfstree.TreeWalkHandler{
-			Item: func(_ btrfstree.TreePath, item btrfstree.Item) error {
+			Item: func(_ btrfstree.Path, item btrfstree.Item) error {
 				if item.Key.ItemType != btrfsitem.ROOT_ITEM_KEY {
 					return nil
 				}
@@ -99,12 +99,12 @@ var nodeHeaderSize = binstruct.StaticSize(btrfstree.NodeHeader{})
 func printTree(ctx context.Context, out io.Writer, fs *btrfs.FS, treeID btrfsprim.ObjID) {
 	var itemOffset uint32
 	handlers := btrfstree.TreeWalkHandler{
-		Node: func(path btrfstree.TreePath, node *btrfstree.Node) error {
+		Node: func(path btrfstree.Path, node *btrfstree.Node) error {
 			printHeaderInfo(out, node)
 			itemOffset = node.Size - uint32(nodeHeaderSize)
 			return nil
 		},
-		PreKeyPointer: func(path btrfstree.TreePath, item btrfstree.KeyPointer) error {
+		PreKeyPointer: func(path btrfstree.Path, item btrfstree.KeyPointer) error {
 			treeID := path[0].FromTree
 			textui.Fprintf(out, "\tkey %v block %v gen %v\n",
 				item.Key.Format(treeID),
@@ -112,7 +112,7 @@ func printTree(ctx context.Context, out io.Writer, fs *btrfs.FS, treeID btrfspri
 				item.Generation)
 			return nil
 		},
-		Item: func(path btrfstree.TreePath, item btrfstree.Item) error {
+		Item: func(path btrfstree.Path, item btrfstree.Item) error {
 			treeID := path[0].FromTree
 			i := path.Node(-1).FromItemSlot
 			bs, _ := binstruct.Marshal(item.Body)
diff --git a/cmd/btrfs-rec/inspect_lstrees.go b/cmd/btrfs-rec/inspect_lstrees.go
index 70f4f51..1541012 100644
--- a/cmd/btrfs-rec/inspect_lstrees.go
+++ b/cmd/btrfs-rec/inspect_lstrees.go
@@ -75,16 +75,16 @@ func init() {
 					treeErrCnt++
 				},
 				TreeWalkHandler: btrfstree.TreeWalkHandler{
-					Node: func(path btrfstree.TreePath, node *btrfstree.Node) error {
+					Node: func(path btrfstree.Path, node *btrfstree.Node) error {
 						visitedNodes.Insert(path.Node(-1).ToNodeAddr)
 						return nil
 					},
-					Item: func(_ btrfstree.TreePath, item btrfstree.Item) error {
+					Item: func(_ btrfstree.Path, item btrfstree.Item) error {
 						typ := item.Key.ItemType
 						treeItemCnt[typ]++
 						return nil
 					},
-					BadItem: func(_ btrfstree.TreePath, item btrfstree.Item) error {
+					BadItem: func(_ btrfstree.Path, item btrfstree.Item) error {
 						typ := item.Key.ItemType
 						treeItemCnt[typ]++
 						return nil
diff --git a/cmd/btrfs-rec/inspect_spewitems.go b/cmd/btrfs-rec/inspect_spewitems.go
index d8a65ae..b83e989 100644
--- a/cmd/btrfs-rec/inspect_spewitems.go
+++ b/cmd/btrfs-rec/inspect_spewitems.go
@@ -34,13 +34,13 @@ func init() {
 					dlog.Error(ctx, err)
 				},
 				TreeWalkHandler: btrfstree.TreeWalkHandler{
-					Item: func(path btrfstree.TreePath, item btrfstree.Item) error {
+					Item: func(path btrfstree.Path, item btrfstree.Item) error {
 						textui.Fprintf(os.Stdout, "%s = ", path)
 						spew.Dump(item)
 						_, _ = os.Stdout.WriteString("\n")
 						return nil
 					},
-					BadItem: func(path btrfstree.TreePath, item btrfstree.Item) error {
+					BadItem: func(path btrfstree.Path, item btrfstree.Item) error {
 						textui.Fprintf(os.Stdout, "%s = ", path)
 						spew.Dump(item)
 						_, _ = os.Stdout.WriteString("\n")
diff --git a/lib/btrfs/btrfstree/btree.go b/lib/btrfs/btrfstree/btree.go
index c71aad5..e91fcc1 100644
--- a/lib/btrfs/btrfstree/btree.go
+++ b/lib/btrfs/btrfstree/btree.go
@@ -69,20 +69,20 @@ type TreeWalkHandler struct {
 	// node immediately stops getting processed; if PreNode, Node,
 	// or BadNode return io/fs.SkipDir then key pointers and items
 	// within the node are not processed.
-	PreNode  func(TreePath) error
-	Node     func(TreePath, *Node) error
-	BadNode  func(TreePath, *Node, error) error
-	PostNode func(TreePath, *Node) error
+	PreNode  func(Path) error
+	Node     func(Path, *Node) error
+	BadNode  func(Path, *Node, error) error
+	PostNode func(Path, *Node) error
 	// Callbacks for items on interior nodes
-	PreKeyPointer  func(TreePath, KeyPointer) error
-	PostKeyPointer func(TreePath, KeyPointer) error
+	PreKeyPointer  func(Path, KeyPointer) error
+	PostKeyPointer func(Path, KeyPointer) error
 	// Callbacks for items on leaf nodes
-	Item    func(TreePath, Item) error
-	BadItem func(TreePath, Item) error
+	Item    func(Path, Item) error
+	BadItem func(Path, Item) error
 }
 
 type TreeError struct {
-	Path TreePath
+	Path Path
 	Err  error
 }
 
@@ -94,5 +94,5 @@ func (e *TreeError) Error() string {
 
 type NodeSource interface {
 	Superblock() (*Superblock, error)
-	ReadNode(TreePath) (*Node, error)
+	ReadNode(Path) (*Node, error)
 }
diff --git a/lib/btrfs/btrfstree/btree_tree.go b/lib/btrfs/btrfstree/btree_tree.go
index 7561314..459f481 100644
--- a/lib/btrfs/btrfstree/btree_tree.go
+++ b/lib/btrfs/btrfstree/btree_tree.go
@@ -26,11 +26,11 @@ type TreeOperatorImpl struct {
 func (fs TreeOperatorImpl) TreeWalk(ctx context.Context, treeID btrfsprim.ObjID, errHandle func(*TreeError), cbs TreeWalkHandler) {
 	sb, err := fs.Superblock()
 	if err != nil {
-		errHandle(&TreeError{Path: TreePath{{FromTree: treeID, ToMaxKey: btrfsprim.MaxKey}}, Err: err})
+		errHandle(&TreeError{Path: Path{{FromTree: treeID, ToMaxKey: btrfsprim.MaxKey}}, Err: err})
 	}
 	rootInfo, err := LookupTreeRoot(fs, *sb, treeID)
 	if err != nil {
-		errHandle(&TreeError{Path: TreePath{{FromTree: treeID, ToMaxKey: btrfsprim.MaxKey}}, Err: err})
+		errHandle(&TreeError{Path: Path{{FromTree: treeID, ToMaxKey: btrfsprim.MaxKey}}, Err: err})
 		return
 	}
 	fs.RawTreeWalk(ctx, *rootInfo, errHandle, cbs)
@@ -39,7 +39,7 @@ func (fs TreeOperatorImpl) TreeWalk(ctx context.Context, treeID btrfsprim.ObjID,
 // RawTreeWalk is a utility method to help with implementing the
 // 'TreeOperator' interface.
 func (fs TreeOperatorImpl) RawTreeWalk(ctx context.Context, rootInfo TreeRoot, errHandle func(*TreeError), cbs TreeWalkHandler) {
-	path := TreePath{{
+	path := Path{{
 		FromTree:         rootInfo.TreeID,
 		FromItemSlot:     -1,
 		ToNodeAddr:       rootInfo.RootNode,
@@ -50,7 +50,7 @@ func (fs TreeOperatorImpl) RawTreeWalk(ctx context.Context, rootInfo TreeRoot, e
 	fs.treeWalk(ctx, path, errHandle, cbs)
 }
 
-func (fs TreeOperatorImpl) treeWalk(ctx context.Context, path TreePath, errHandle func(*TreeError), cbs TreeWalkHandler) {
+func (fs TreeOperatorImpl) treeWalk(ctx context.Context, path Path, errHandle func(*TreeError), cbs TreeWalkHandler) {
 	if ctx.Err() != nil {
 		return
 	}
@@ -100,7 +100,7 @@ func (fs TreeOperatorImpl) treeWalk(ctx context.Context, path TreePath, errHandl
 			if i+1 < len(node.BodyInterior) {
 				toMaxKey = node.BodyInterior[i+1].Key.Mm()
 			}
-			itemPath := append(path, TreePathElem{
+			itemPath := append(path, PathElem{
 				FromTree:         node.Head.Owner,
 				FromItemSlot:     i,
 				ToNodeAddr:       item.BlockPtr,
@@ -128,7 +128,7 @@ func (fs TreeOperatorImpl) treeWalk(ctx context.Context, path TreePath, errHandl
 			}
 		}
 		for i, item := range node.BodyLeaf {
-			itemPath := append(path, TreePathElem{
+			itemPath := append(path, PathElem{
 				FromTree:     node.Head.Owner,
 				FromItemSlot: i,
 				ToKey:        item.Key,
@@ -167,8 +167,8 @@ func (fs TreeOperatorImpl) treeWalk(ctx context.Context, path TreePath, errHandl
 	}
 }
 
-func (fs TreeOperatorImpl) treeSearch(treeRoot TreeRoot, fn func(btrfsprim.Key, uint32) int) (TreePath, *Node, error) {
-	path := TreePath{{
+func (fs TreeOperatorImpl) treeSearch(treeRoot TreeRoot, fn func(btrfsprim.Key, uint32) int) (Path, *Node, error) {
+	path := Path{{
 		FromTree:         treeRoot.TreeID,
 		FromItemSlot:     -1,
 		ToNodeAddr:       treeRoot.RootNode,
@@ -209,7 +209,7 @@ func (fs TreeOperatorImpl) treeSearch(treeRoot TreeRoot, fn func(btrfsprim.Key,
 			if lastGood+1 < len(node.BodyInterior) {
 				toMaxKey = node.BodyInterior[lastGood+1].Key.Mm()
 			}
-			path = append(path, TreePathElem{
+			path = append(path, PathElem{
 				FromTree:         node.Head.Owner,
 				FromItemSlot:     lastGood,
 				ToNodeAddr:       node.BodyInterior[lastGood].BlockPtr,
@@ -239,7 +239,7 @@ func (fs TreeOperatorImpl) treeSearch(treeRoot TreeRoot, fn func(btrfsprim.Key,
 				node.Free()
 				return nil, nil, ErrNoItem
 			}
-			path = append(path, TreePathElem{
+			path = append(path, PathElem{
 				FromTree:     node.Head.Owner,
 				FromItemSlot: slot,
 				ToKey:        node.BodyLeaf[slot].Key,
@@ -250,7 +250,7 @@ func (fs TreeOperatorImpl) treeSearch(treeRoot TreeRoot, fn func(btrfsprim.Key,
 	}
 }
 
-func (fs TreeOperatorImpl) prev(path TreePath, node *Node) (TreePath, *Node, error) {
+func (fs TreeOperatorImpl) prev(path Path, node *Node) (Path, *Node, error) {
 	var err error
 	path = path.DeepCopy()
 
@@ -285,7 +285,7 @@ func (fs TreeOperatorImpl) prev(path TreePath, node *Node) (TreePath, *Node, err
 			}
 		}
 		if node.Head.Level > 0 {
-			path = append(path, TreePathElem{
+			path = append(path, PathElem{
 				FromTree:         node.Head.Owner,
 				FromItemSlot:     len(node.BodyInterior) - 1,
 				ToNodeAddr:       node.BodyInterior[len(node.BodyInterior)-1].BlockPtr,
@@ -295,7 +295,7 @@ func (fs TreeOperatorImpl) prev(path TreePath, node *Node) (TreePath, *Node, err
 				ToMaxKey:         path.Node(-1).ToMaxKey,
 			})
 		} else {
-			path = append(path, TreePathElem{
+			path = append(path, PathElem{
 				FromTree:     node.Head.Owner,
 				FromItemSlot: len(node.BodyLeaf) - 1,
 				ToKey:        node.BodyLeaf[len(node.BodyLeaf)-1].Key,
@@ -315,7 +315,7 @@ func (fs TreeOperatorImpl) prev(path TreePath, node *Node) (TreePath, *Node, err
 	return path, node, nil
 }
 
-func (fs TreeOperatorImpl) next(path TreePath, node *Node) (TreePath, *Node, error) {
+func (fs TreeOperatorImpl) next(path Path, node *Node) (Path, *Node, error) {
 	var err error
 	path = path.DeepCopy()
 
@@ -373,7 +373,7 @@ func (fs TreeOperatorImpl) next(path TreePath, node *Node) (TreePath, *Node, err
 			if len(node.BodyInterior) > 1 {
 				toMaxKey = node.BodyInterior[1].Key.Mm()
 			}
-			path = append(path, TreePathElem{
+			path = append(path, PathElem{
 				FromTree:         node.Head.Owner,
 				FromItemSlot:     0,
 				ToNodeAddr:       node.BodyInterior[0].BlockPtr,
@@ -383,7 +383,7 @@ func (fs TreeOperatorImpl) next(path TreePath, node *Node) (TreePath, *Node, err
 				ToMaxKey:         toMaxKey,
 			})
 		} else {
-			path = append(path, TreePathElem{
+			path = append(path, PathElem{
 				FromTree:     node.Head.Owner,
 				FromItemSlot: 0,
 				ToKey:        node.BodyInterior[0].Key,
diff --git a/lib/btrfs/btrfstree/path.go b/lib/btrfs/btrfstree/path.go
index b9ab5bc..c07d8a0 100644
--- a/lib/btrfs/btrfstree/path.go
+++ b/lib/btrfs/btrfstree/path.go
@@ -13,7 +13,7 @@ import (
 	"git.lukeshu.com/btrfs-progs-ng/lib/btrfs/btrfsvol"
 )
 
-// TreePath is a path from the superblock (i.e. the root of the btrfs
+// Path is a path from the superblock (i.e. the root of the btrfs
 // system) to the a node or item within one of the btrees in the
 // system.
 //
@@ -61,10 +61,10 @@ import (
 //	                                | <--------------- pathElem={from_tree:A, from_slot:1,
 //	                                |                            to_addr:0, to_gen: 0, to_lvl:0}
 //	                              [item]
-type TreePath []TreePathElem
+type Path []PathElem
 
-// A TreePathElem essentially represents a KeyPointer.
-type TreePathElem struct {
+// A PathElem essentially represents a KeyPointer.
+type PathElem struct {
 	// FromTree is the owning tree ID of the parent node; or the
 	// well-known tree ID if this is the root.
 	FromTree btrfsprim.ObjID
@@ -94,17 +94,17 @@ type TreePathElem struct {
 	ToMaxKey btrfsprim.Key
 }
 
-func (elem TreePathElem) writeNodeTo(w io.Writer) {
+func (elem PathElem) writeNodeTo(w io.Writer) {
 	fmt.Fprintf(w, "node:%d@%v", elem.ToNodeLevel, elem.ToNodeAddr)
 }
 
-func (path TreePath) String() string {
+func (path Path) String() string {
 	if len(path) == 0 {
 		return "(empty-path)"
 	}
 	var ret strings.Builder
 	fmt.Fprintf(&ret, "%s->", path[0].FromTree.Format(btrfsprim.ROOT_TREE_OBJECTID))
-	if len(path) == 1 && path[0] == (TreePathElem{FromTree: path[0].FromTree, FromItemSlot: -1}) {
+	if len(path) == 1 && path[0] == (PathElem{FromTree: path[0].FromTree, FromItemSlot: -1}) {
 		ret.WriteString("(empty-path)")
 	} else {
 		path[0].writeNodeTo(&ret)
@@ -119,11 +119,11 @@ func (path TreePath) String() string {
 	return ret.String()
 }
 
-func (path TreePath) DeepCopy() TreePath {
-	return append(TreePath(nil), path...)
+func (path Path) DeepCopy() Path {
+	return append(Path(nil), path...)
 }
 
-func (path TreePath) Parent() TreePath {
+func (path Path) Parent() Path {
 	return path[:len(path)-1]
 }
 
@@ -131,7 +131,7 @@ func (path TreePath) Parent() TreePath {
 // `&path[x]`, but negative values of x move down from the end of path
 // (similar to how lists work in many other languages, such as
 // Python).
-func (path TreePath) Node(x int) *TreePathElem {
+func (path Path) Node(x int) *PathElem {
 	if x < 0 {
 		x += len(path)
 	}
diff --git a/lib/btrfs/btrfstree/readnode.go b/lib/btrfs/btrfstree/readnode.go
index 1c242ac..c5d9145 100644
--- a/lib/btrfs/btrfstree/readnode.go
+++ b/lib/btrfs/btrfstree/readnode.go
@@ -33,7 +33,7 @@ type NodeFile interface {
 // 'NodeSource' interface.
 func FSReadNode(
 	fs NodeFile,
-	path TreePath,
+	path Path,
 ) (*Node, error) {
 	sb, err := fs.Superblock()
 	if err != nil {
diff --git a/lib/btrfs/io2_lv.go b/lib/btrfs/io2_lv.go
index 856ac20..d05d51f 100644
--- a/lib/btrfs/io2_lv.go
+++ b/lib/btrfs/io2_lv.go
@@ -168,7 +168,7 @@ func (fs *FS) initDev(ctx context.Context, sb btrfstree.Superblock) error {
 			errs = append(errs, err)
 		},
 		btrfstree.TreeWalkHandler{
-			Item: func(_ btrfstree.TreePath, item btrfstree.Item) error {
+			Item: func(_ btrfstree.Path, item btrfstree.Item) error {
 				if item.Key.ItemType != btrfsitem.CHUNK_ITEM_KEY {
 					return nil
 				}
diff --git a/lib/btrfs/io3_btree.go b/lib/btrfs/io3_btree.go
index 467bbde..80ab10f 100644
--- a/lib/btrfs/io3_btree.go
+++ b/lib/btrfs/io3_btree.go
@@ -17,7 +17,7 @@ import (
 // btrfstree.NodeSource ////////////////////////////////////////////////////////
 
 // ReadNode implements btrfstree.NodeSource.
-func (fs *FS) ReadNode(path btrfstree.TreePath) (*btrfstree.Node, error) {
+func (fs *FS) ReadNode(path btrfstree.Path) (*btrfstree.Node, error) {
 	return btrfstree.FSReadNode(fs, path)
 }
 
@@ -37,7 +37,7 @@ func (fs *FS) populateTreeUUIDs(ctx context.Context) {
 			// do nothing
 		},
 		btrfstree.TreeWalkHandler{
-			Item: func(_ btrfstree.TreePath, item btrfstree.Item) error {
+			Item: func(_ btrfstree.Path, item btrfstree.Item) error {
 				itemBody, ok := item.Body.(*btrfsitem.Root)
 				if !ok {
 					return nil
diff --git a/lib/btrfsutil/old_rebuilt_forrest.go b/lib/btrfsutil/old_rebuilt_forrest.go
index 8bc02df..5f6c718 100644
--- a/lib/btrfsutil/old_rebuilt_forrest.go
+++ b/lib/btrfsutil/old_rebuilt_forrest.go
@@ -178,7 +178,7 @@ 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 {
+		BadNode: func(path btrfstree.Path, node *btrfstree.Node, err error) error {
 			if node != nil {
 				curNode = nodeInfo{
 					LAddr:      path.Node(-1).ToNodeAddr,
@@ -191,7 +191,7 @@ func (bt *OldRebuiltForrest) rawTreeWalk(root btrfstree.TreeRoot, cacheEntry old
 			}
 			return err
 		},
-		Node: func(path btrfstree.TreePath, node *btrfstree.Node) error {
+		Node: func(path btrfstree.Path, node *btrfstree.Node) error {
 			curNode = nodeInfo{
 				LAddr:      path.Node(-1).ToNodeAddr,
 				Level:      node.Head.Level,
@@ -202,7 +202,7 @@ func (bt *OldRebuiltForrest) rawTreeWalk(root btrfstree.TreeRoot, cacheEntry old
 			}
 			return nil
 		},
-		Item: func(path btrfstree.TreePath, item btrfstree.Item) error {
+		Item: func(path btrfstree.Path, 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
 				// handle this is, and so if this happens I want the program to crash
@@ -340,7 +340,7 @@ func (bt *OldRebuiltForrest) TreeWalk(ctx context.Context, treeID btrfsprim.ObjI
 	tree := bt.RebuiltTree(treeID)
 	if tree.RootErr != nil {
 		errHandle(&btrfstree.TreeError{
-			Path: btrfstree.TreePath{{
+			Path: btrfstree.Path{{
 				FromTree: treeID,
 				ToMaxKey: btrfsprim.MaxKey,
 			}},
@@ -365,7 +365,7 @@ func (bt *OldRebuiltForrest) TreeWalk(ctx context.Context, treeID btrfsprim.ObjI
 		}
 		item := node.BodyLeaf[indexItem.Value.Slot]
 
-		itemPath := btrfstree.TreePath{
+		itemPath := btrfstree.Path{
 			{
 				FromTree:         treeID,
 				ToNodeAddr:       indexItem.Value.Node.LAddr,
diff --git a/lib/btrfsutil/rebuilt_forrest.go b/lib/btrfsutil/rebuilt_forrest.go
index 70ece13..0e8f5ad 100644
--- a/lib/btrfsutil/rebuilt_forrest.go
+++ b/lib/btrfsutil/rebuilt_forrest.go
@@ -40,7 +40,7 @@ type RebuiltForrestCallbacks interface {
 //   - it consumes an already-read Graph instead of reading the graph
 //     itself
 //
-//   - it does not use `btrfstree.TreePath`
+//   - it does not use `btrfstree.Path`
 //
 //   - it does not keep track of errors encountered in a tree
 //
diff --git a/lib/btrfsutil/walk.go b/lib/btrfsutil/walk.go
index 355976a..bbdf992 100644
--- a/lib/btrfsutil/walk.go
+++ b/lib/btrfsutil/walk.go
@@ -1,4 +1,4 @@
-// Copyright (C) 2022  Luke Shumaker <lukeshu@lukeshu.com>
+// Copyright (C) 2022-2023  Luke Shumaker <lukeshu@lukeshu.com>
 //
 // SPDX-License-Identifier: GPL-2.0-or-later
 
@@ -61,7 +61,7 @@ func WalkAllTrees(ctx context.Context, fs btrfstree.TreeOperator, cbs WalkAllTre
 		},
 	}
 	origItem := cbs.Item
-	cbs.Item = func(path btrfstree.TreePath, item btrfstree.Item) error {
+	cbs.Item = func(path btrfstree.Path, item btrfstree.Item) error {
 		if item.Key.ItemType == btrfsitem.ROOT_ITEM_KEY {
 			trees = append(trees, struct {
 				Name string
-- 
cgit v1.2.3-54-g00ecf


From ceb9041cc7c838b3833ebc20cd97b02fbd3c92b3 Mon Sep 17 00:00:00 2001
From: Luke Shumaker <lukeshu@lukeshu.com>
Date: Thu, 2 Mar 2023 20:43:48 -0700
Subject: btrfsutil: OldRebuildForrest: Drop the Augment method

---
 lib/btrfsutil/old_rebuilt_forrest.go | 31 ++-----------------------------
 1 file changed, 2 insertions(+), 29 deletions(-)

(limited to 'lib/btrfsutil/old_rebuilt_forrest.go')

diff --git a/lib/btrfsutil/old_rebuilt_forrest.go b/lib/btrfsutil/old_rebuilt_forrest.go
index 5f6c718..f59a1f9 100644
--- a/lib/btrfsutil/old_rebuilt_forrest.go
+++ b/lib/btrfsutil/old_rebuilt_forrest.go
@@ -148,7 +148,7 @@ func (bt *OldRebuiltForrest) RebuiltTree(treeID btrfsprim.ObjID) oldRebuiltTree
 		cacheEntry.RootErr = err
 	} else {
 		dlog.Infof(bt.ctx, "indexing tree %v...", treeID)
-		bt.rawTreeWalk(*treeRoot, cacheEntry, nil)
+		bt.rawTreeWalk(*treeRoot, cacheEntry)
 		dlog.Infof(bt.ctx, "... done indexing tree %v", treeID)
 	}
 
@@ -162,7 +162,7 @@ func (bt *OldRebuiltForrest) RebuiltTree(treeID btrfsprim.ObjID) oldRebuiltTree
 
 func discardOK[T any](x T, _ bool) T { return x }
 
-func (bt *OldRebuiltForrest) rawTreeWalk(root btrfstree.TreeRoot, cacheEntry oldRebuiltTree, walked *[]btrfsprim.Key) {
+func (bt *OldRebuiltForrest) rawTreeWalk(root btrfstree.TreeRoot, cacheEntry oldRebuiltTree) {
 	errHandle := func(err *btrfstree.TreeError) {
 		if len(err.Path) > 0 && err.Path.Node(-1).ToNodeAddr == 0 {
 			// This is a panic because on the filesystems I'm working with it more likely
@@ -216,9 +216,6 @@ func (bt *OldRebuiltForrest) rawTreeWalk(root btrfstree.TreeRoot, cacheEntry old
 				Node: curNode,
 				Slot: path.Node(-1).FromItemSlot,
 			})
-			if walked != nil {
-				*walked = append(*walked, item.Key)
-			}
 			return nil
 		},
 	}
@@ -396,27 +393,3 @@ func (bt *OldRebuiltForrest) Superblock() (*btrfstree.Superblock, error) {
 func (bt *OldRebuiltForrest) ReadAt(p []byte, off btrfsvol.LogicalAddr) (int, error) {
 	return bt.inner.ReadAt(p, off)
 }
-
-func (bt *OldRebuiltForrest) Augment(treeID btrfsprim.ObjID, nodeAddr btrfsvol.LogicalAddr) ([]btrfsprim.Key, error) {
-	sb, err := bt.Superblock()
-	if err != nil {
-		return nil, err
-	}
-	tree := bt.RebuiltTree(treeID)
-	if tree.RootErr != nil {
-		return nil, tree.RootErr
-	}
-	node, err := btrfstree.ReadNode[btrfsvol.LogicalAddr](bt.inner, *sb, nodeAddr, btrfstree.NodeExpectations{})
-	defer node.Free()
-	if err != nil {
-		return nil, err
-	}
-	var ret []btrfsprim.Key
-	bt.rawTreeWalk(btrfstree.TreeRoot{
-		TreeID:     treeID,
-		RootNode:   nodeAddr,
-		Level:      node.Head.Level,
-		Generation: node.Head.Generation,
-	}, tree, &ret)
-	return ret, nil
-}
-- 
cgit v1.2.3-54-g00ecf


From 26e58f1cd1d47b63b1b05b26c73c4f69f7e245cb Mon Sep 17 00:00:00 2001
From: Luke Shumaker <lukeshu@lukeshu.com>
Date: Mon, 13 Mar 2023 18:52:51 -0600
Subject: btrfsutil: OldRebuiltForrest: Hoist logic from .RebuiltTree to
 .rawTreeWalk

It's OK that for ROOT_TREE_OBJECTID it now calls btrfstree.LookupTreeRoot
on `bt` instead of `bt.inner`, because LookupTreeRoot doesn't actually use
that argument for ROOT_TREE_OBJECTID.
---
 lib/btrfsutil/old_rebuilt_forrest.go | 36 ++++++++++++++++--------------------
 1 file changed, 16 insertions(+), 20 deletions(-)

(limited to 'lib/btrfsutil/old_rebuilt_forrest.go')

diff --git a/lib/btrfsutil/old_rebuilt_forrest.go b/lib/btrfsutil/old_rebuilt_forrest.go
index f59a1f9..c146935 100644
--- a/lib/btrfsutil/old_rebuilt_forrest.go
+++ b/lib/btrfsutil/old_rebuilt_forrest.go
@@ -115,19 +115,12 @@ func NewOldRebuiltForrest(ctx context.Context, inner *btrfs.FS) *OldRebuiltForre
 }
 
 func (bt *OldRebuiltForrest) RebuiltTree(treeID btrfsprim.ObjID) oldRebuiltTree {
-	var treeRoot *btrfstree.TreeRoot
-	var sb *btrfstree.Superblock
-	var err error
 	if treeID == btrfsprim.ROOT_TREE_OBJECTID {
 		bt.rootTreeMu.Lock()
 		defer bt.rootTreeMu.Unlock()
 		if bt.rootTree != nil {
 			return *bt.rootTree
 		}
-		sb, err = bt.inner.Superblock()
-		if err == nil {
-			treeRoot, err = btrfstree.LookupTreeRoot(bt.inner, *sb, treeID)
-		}
 	} else {
 		bt.treesMu.Lock()
 		defer bt.treesMu.Unlock()
@@ -137,20 +130,12 @@ func (bt *OldRebuiltForrest) RebuiltTree(treeID btrfsprim.ObjID) oldRebuiltTree
 		if cacheEntry, exists := bt.trees[treeID]; exists {
 			return cacheEntry
 		}
-		sb, err = bt.inner.Superblock()
-		if err == nil {
-			treeRoot, err = btrfstree.LookupTreeRoot(bt, *sb, treeID)
-		}
 	}
 
 	cacheEntry := newOldRebuiltTree()
-	if err != nil {
-		cacheEntry.RootErr = err
-	} else {
-		dlog.Infof(bt.ctx, "indexing tree %v...", treeID)
-		bt.rawTreeWalk(*treeRoot, cacheEntry)
-		dlog.Infof(bt.ctx, "... done indexing tree %v", treeID)
-	}
+	dlog.Infof(bt.ctx, "indexing tree %v...", treeID)
+	bt.rawTreeWalk(treeID, &cacheEntry)
+	dlog.Infof(bt.ctx, "... done indexing tree %v", treeID)
 
 	if treeID == btrfsprim.ROOT_TREE_OBJECTID {
 		bt.rootTree = &cacheEntry
@@ -162,7 +147,18 @@ func (bt *OldRebuiltForrest) RebuiltTree(treeID btrfsprim.ObjID) oldRebuiltTree
 
 func discardOK[T any](x T, _ bool) T { return x }
 
-func (bt *OldRebuiltForrest) rawTreeWalk(root btrfstree.TreeRoot, cacheEntry oldRebuiltTree) {
+func (bt *OldRebuiltForrest) rawTreeWalk(treeID btrfsprim.ObjID, cacheEntry *oldRebuiltTree) {
+	sb, err := bt.inner.Superblock()
+	if err != nil {
+		cacheEntry.RootErr = err
+		return
+	}
+	root, err := btrfstree.LookupTreeRoot(bt, *sb, treeID)
+	if err != nil {
+		cacheEntry.RootErr = err
+		return
+	}
+
 	errHandle := func(err *btrfstree.TreeError) {
 		if len(err.Path) > 0 && err.Path.Node(-1).ToNodeAddr == 0 {
 			// This is a panic because on the filesystems I'm working with it more likely
@@ -220,7 +216,7 @@ func (bt *OldRebuiltForrest) rawTreeWalk(root btrfstree.TreeRoot, cacheEntry old
 		},
 	}
 
-	btrfstree.TreeOperatorImpl{NodeSource: bt.inner}.RawTreeWalk(bt.ctx, root, errHandle, cbs)
+	btrfstree.TreeOperatorImpl{NodeSource: bt.inner}.RawTreeWalk(bt.ctx, *root, errHandle, cbs)
 }
 
 func (bt *OldRebuiltForrest) TreeLookup(treeID btrfsprim.ObjID, key btrfsprim.Key) (btrfstree.Item, error) {
-- 
cgit v1.2.3-54-g00ecf


From 33de7f09d31063ef2a4380bb2f2692653a6de06c Mon Sep 17 00:00:00 2001
From: Luke Shumaker <lukeshu@lukeshu.com>
Date: Thu, 9 Mar 2023 16:43:39 -0700
Subject: containers: Add OptionalValue and OptionalNil

---
 cmd/btrfs-rec/inspect/rebuildmappings/process.go            |  5 +----
 .../inspect/rebuildmappings/process_matchsums_exact.go      |  5 +----
 .../inspect/rebuildmappings/process_matchsums_fuzzy.go      |  5 +----
 cmd/btrfs-rec/inspect/rebuildtrees/scan.go                  |  2 +-
 cmd/btrfs-rec/inspect_lstrees.go                            |  2 +-
 lib/btrfs/btrfsitem/item_chunk.go                           |  5 +----
 lib/btrfs/btrfstree/readnode.go                             | 10 +++++-----
 lib/btrfsutil/graph.go                                      |  2 +-
 lib/btrfsutil/old_rebuilt_forrest.go                        | 10 +++++-----
 lib/btrfsutil/rebuilt_readitem.go                           | 10 +++++-----
 lib/containers/optional.go                                  | 13 +++++++++++++
 11 files changed, 35 insertions(+), 34 deletions(-)

(limited to 'lib/btrfsutil/old_rebuilt_forrest.go')

diff --git a/cmd/btrfs-rec/inspect/rebuildmappings/process.go b/cmd/btrfs-rec/inspect/rebuildmappings/process.go
index e42acf9..7a49cc6 100644
--- a/cmd/btrfs-rec/inspect/rebuildmappings/process.go
+++ b/cmd/btrfs-rec/inspect/rebuildmappings/process.go
@@ -137,10 +137,7 @@ func RebuildMappings(ctx context.Context, fs *btrfs.FS, scanResults ScanDevicesR
 			PAddr:      otherPAddr.Add(-offsetWithinChunk),
 			Size:       bg.Size,
 			SizeLocked: true,
-			Flags: containers.Optional[btrfsvol.BlockGroupFlags]{
-				OK:  true,
-				Val: bg.Flags,
-			},
+			Flags:      containers.OptionalValue(bg.Flags),
 		}
 		if err := fs.LV.AddMapping(mapping); err != nil {
 			dlog.Errorf(ctx, "error: adding flags from blockgroup: %v", err)
diff --git a/cmd/btrfs-rec/inspect/rebuildmappings/process_matchsums_exact.go b/cmd/btrfs-rec/inspect/rebuildmappings/process_matchsums_exact.go
index ef9d9aa..5148e5c 100644
--- a/cmd/btrfs-rec/inspect/rebuildmappings/process_matchsums_exact.go
+++ b/cmd/btrfs-rec/inspect/rebuildmappings/process_matchsums_exact.go
@@ -63,10 +63,7 @@ func matchBlockGroupSumsExact(ctx context.Context,
 			PAddr:      matches[0],
 			Size:       blockgroup.Size,
 			SizeLocked: true,
-			Flags: containers.Optional[btrfsvol.BlockGroupFlags]{
-				OK:  true,
-				Val: blockgroup.Flags,
-			},
+			Flags:      containers.OptionalValue(blockgroup.Flags),
 		}
 		if err := fs.LV.AddMapping(mapping); err != nil {
 			dlog.Errorf(ctx, "error: %v", err)
diff --git a/cmd/btrfs-rec/inspect/rebuildmappings/process_matchsums_fuzzy.go b/cmd/btrfs-rec/inspect/rebuildmappings/process_matchsums_fuzzy.go
index 905211c..f3557cd 100644
--- a/cmd/btrfs-rec/inspect/rebuildmappings/process_matchsums_fuzzy.go
+++ b/cmd/btrfs-rec/inspect/rebuildmappings/process_matchsums_fuzzy.go
@@ -123,10 +123,7 @@ func matchBlockGroupSumsFuzzy(ctx context.Context,
 			PAddr:      best.Dat[0].PAddr,
 			Size:       blockgroup.Size,
 			SizeLocked: true,
-			Flags: containers.Optional[btrfsvol.BlockGroupFlags]{
-				OK:  true,
-				Val: blockgroup.Flags,
-			},
+			Flags:      containers.OptionalValue(blockgroup.Flags),
 		}
 		if err := fs.LV.AddMapping(mapping); err != nil {
 			dlog.Errorf(ctx, "error: %v", err)
diff --git a/cmd/btrfs-rec/inspect/rebuildtrees/scan.go b/cmd/btrfs-rec/inspect/rebuildtrees/scan.go
index 961ff8d..ada9f6f 100644
--- a/cmd/btrfs-rec/inspect/rebuildtrees/scan.go
+++ b/cmd/btrfs-rec/inspect/rebuildtrees/scan.go
@@ -72,7 +72,7 @@ func ScanDevices(ctx context.Context, fs *btrfs.FS, nodeList []btrfsvol.LogicalA
 			return ScanDevicesResult{}, err
 		}
 		node, err := btrfstree.ReadNode[btrfsvol.LogicalAddr](fs, *sb, laddr, btrfstree.NodeExpectations{
-			LAddr: containers.Optional[btrfsvol.LogicalAddr]{OK: true, Val: laddr},
+			LAddr: containers.OptionalValue(laddr),
 		})
 		if err != nil {
 			node.Free()
diff --git a/cmd/btrfs-rec/inspect_lstrees.go b/cmd/btrfs-rec/inspect_lstrees.go
index 1541012..cad1a37 100644
--- a/cmd/btrfs-rec/inspect_lstrees.go
+++ b/cmd/btrfs-rec/inspect_lstrees.go
@@ -106,7 +106,7 @@ func init() {
 					}
 					visitedNodes.Insert(laddr)
 					node, err := btrfstree.ReadNode[btrfsvol.LogicalAddr](fs, *sb, laddr, btrfstree.NodeExpectations{
-						LAddr: containers.Optional[btrfsvol.LogicalAddr]{OK: true, Val: laddr},
+						LAddr: containers.OptionalValue(laddr),
 					})
 					if err != nil {
 						treeErrCnt++
diff --git a/lib/btrfs/btrfsitem/item_chunk.go b/lib/btrfs/btrfsitem/item_chunk.go
index 607df75..9bdef1f 100644
--- a/lib/btrfs/btrfsitem/item_chunk.go
+++ b/lib/btrfs/btrfsitem/item_chunk.go
@@ -61,10 +61,7 @@ func (chunk Chunk) Mappings(key btrfsprim.Key) []btrfsvol.Mapping {
 			},
 			Size:       chunk.Head.Size,
 			SizeLocked: true,
-			Flags: containers.Optional[btrfsvol.BlockGroupFlags]{
-				OK:  true,
-				Val: chunk.Head.Type,
-			},
+			Flags:      containers.OptionalValue(chunk.Head.Type),
 		})
 	}
 	return ret
diff --git a/lib/btrfs/btrfstree/readnode.go b/lib/btrfs/btrfstree/readnode.go
index c5d9145..c2e3b0f 100644
--- a/lib/btrfs/btrfstree/readnode.go
+++ b/lib/btrfs/btrfstree/readnode.go
@@ -63,11 +63,11 @@ func FSReadNode(
 	}
 
 	return ReadNode[btrfsvol.LogicalAddr](fs, *sb, path.Node(-1).ToNodeAddr, NodeExpectations{
-		LAddr:      containers.Optional[btrfsvol.LogicalAddr]{OK: true, Val: path.Node(-1).ToNodeAddr},
-		Level:      containers.Optional[uint8]{OK: true, Val: path.Node(-1).ToNodeLevel},
-		Generation: containers.Optional[btrfsprim.Generation]{OK: true, Val: path.Node(-1).ToNodeGeneration},
+		LAddr:      containers.OptionalValue(path.Node(-1).ToNodeAddr),
+		Level:      containers.OptionalValue(path.Node(-1).ToNodeLevel),
+		Generation: containers.OptionalValue(path.Node(-1).ToNodeGeneration),
 		Owner:      checkOwner,
-		MinItem:    containers.Optional[btrfsprim.Key]{OK: true, Val: path.Node(-1).ToKey},
-		MaxItem:    containers.Optional[btrfsprim.Key]{OK: true, Val: path.Node(-1).ToMaxKey},
+		MinItem:    containers.OptionalValue(path.Node(-1).ToKey),
+		MaxItem:    containers.OptionalValue(path.Node(-1).ToMaxKey),
 	})
 }
diff --git a/lib/btrfsutil/graph.go b/lib/btrfsutil/graph.go
index 45e9878..35848de 100644
--- a/lib/btrfsutil/graph.go
+++ b/lib/btrfsutil/graph.go
@@ -209,7 +209,7 @@ func (g Graph) FinalCheck(ctx context.Context, fs diskio.File[btrfsvol.LogicalAd
 	for laddr := range g.EdgesTo {
 		if _, ok := g.Nodes[laddr]; !ok {
 			_, err := btrfstree.ReadNode[btrfsvol.LogicalAddr](fs, sb, laddr, btrfstree.NodeExpectations{
-				LAddr: containers.Optional[btrfsvol.LogicalAddr]{OK: true, Val: laddr},
+				LAddr: containers.OptionalValue(laddr),
 			})
 			if err == nil {
 				progressWriter.Done()
diff --git a/lib/btrfsutil/old_rebuilt_forrest.go b/lib/btrfsutil/old_rebuilt_forrest.go
index c146935..abe3329 100644
--- a/lib/btrfsutil/old_rebuilt_forrest.go
+++ b/lib/btrfsutil/old_rebuilt_forrest.go
@@ -247,9 +247,9 @@ func (bt *OldRebuiltForrest) readNode(nodeInfo nodeInfo) *btrfstree.Node {
 	}
 
 	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},
+		LAddr:      containers.OptionalValue(nodeInfo.LAddr),
+		Level:      containers.OptionalValue(nodeInfo.Level),
+		Generation: containers.OptionalValue(nodeInfo.Generation),
 		Owner: func(treeID btrfsprim.ObjID) error {
 			if treeID != nodeInfo.Owner {
 				return fmt.Errorf("expected owner=%v but claims to have owner=%v",
@@ -257,8 +257,8 @@ func (bt *OldRebuiltForrest) readNode(nodeInfo nodeInfo) *btrfstree.Node {
 			}
 			return nil
 		},
-		MinItem: containers.Optional[btrfsprim.Key]{OK: true, Val: nodeInfo.MinItem},
-		MaxItem: containers.Optional[btrfsprim.Key]{OK: true, Val: nodeInfo.MaxItem},
+		MinItem: containers.OptionalValue(nodeInfo.MinItem),
+		MaxItem: containers.OptionalValue(nodeInfo.MaxItem),
 	})
 	if err != nil {
 		panic(fmt.Errorf("should not happen: i/o error: %w", err))
diff --git a/lib/btrfsutil/rebuilt_readitem.go b/lib/btrfsutil/rebuilt_readitem.go
index 68aabdd..ff919f0 100644
--- a/lib/btrfsutil/rebuilt_readitem.go
+++ b/lib/btrfsutil/rebuilt_readitem.go
@@ -39,9 +39,9 @@ func (ts *RebuiltForrest) readNode(ctx context.Context, laddr btrfsvol.LogicalAd
 
 	dlog.Debugf(ctx, "cache-miss node@%v, reading...", laddr)
 	node, err := btrfstree.ReadNode[btrfsvol.LogicalAddr](ts.file, ts.sb, laddr, btrfstree.NodeExpectations{
-		LAddr:      containers.Optional[btrfsvol.LogicalAddr]{OK: true, Val: laddr},
-		Level:      containers.Optional[uint8]{OK: true, Val: graphInfo.Level},
-		Generation: containers.Optional[btrfsprim.Generation]{OK: true, Val: graphInfo.Generation},
+		LAddr:      containers.OptionalValue(laddr),
+		Level:      containers.OptionalValue(graphInfo.Level),
+		Generation: containers.OptionalValue(graphInfo.Generation),
 		Owner: func(treeID btrfsprim.ObjID) error {
 			if treeID != graphInfo.Owner {
 				return fmt.Errorf("expected owner=%v but claims to have owner=%v",
@@ -49,8 +49,8 @@ func (ts *RebuiltForrest) readNode(ctx context.Context, laddr btrfsvol.LogicalAd
 			}
 			return nil
 		},
-		MinItem: containers.Optional[btrfsprim.Key]{OK: true, Val: graphInfo.MinItem()},
-		MaxItem: containers.Optional[btrfsprim.Key]{OK: true, Val: graphInfo.MaxItem()},
+		MinItem: containers.OptionalValue(graphInfo.MinItem()),
+		MaxItem: containers.OptionalValue(graphInfo.MaxItem()),
 	})
 	if err != nil {
 		panic(fmt.Errorf("should not happen: i/o error: %w", err))
diff --git a/lib/containers/optional.go b/lib/containers/optional.go
index 5bb7bb6..26ec494 100644
--- a/lib/containers/optional.go
+++ b/lib/containers/optional.go
@@ -13,6 +13,19 @@ type Optional[T any] struct {
 	Val T
 }
 
+func OptionalValue[T any](val T) Optional[T] {
+	return Optional[T]{
+		OK:  true,
+		Val: val,
+	}
+}
+
+func OptionalNil[T any]() Optional[T] {
+	return Optional[T]{
+		OK: false,
+	}
+}
+
 var (
 	_ json.Marshaler   = Optional[bool]{}
 	_ json.Unmarshaler = (*Optional[bool])(nil)
-- 
cgit v1.2.3-54-g00ecf