Merge branch 'lukeshu/fast'

7 files changed, 73 insertions, 59 deletions

diff --git a/lib/btrfsprogs/btrfsinspect/rebuildnodes/btrees/forrest.go b/lib/btrfsprogs/btrfsinspect/rebuildnodes/btrees/forrest.go
index 45a5bb2..3eeea7f 100644
--- a/lib/btrfsprogs/btrfsinspect/rebuildnodes/btrees/forrest.go
+++ b/lib/btrfsprogs/btrfsinspect/rebuildnodes/btrees/forrest.go
@@ -64,9 +64,9 @@ type RebuiltForrest struct {
 
 	// mutable
 	trees    typedsync.Map[btrfsprim.ObjID, *RebuiltTree]
-	leafs    *containers.LRUCache[btrfsprim.ObjID, map[btrfsvol.LogicalAddr]containers.Set[btrfsvol.LogicalAddr]]
-	incItems *containers.LRUCache[btrfsprim.ObjID, *itemIndex]
-	excItems *containers.LRUCache[btrfsprim.ObjID, *itemIndex]
+	leafs    containers.ARCache[btrfsprim.ObjID, map[btrfsvol.LogicalAddr]containers.Set[btrfsvol.LogicalAddr]]
+	incItems containers.ARCache[btrfsprim.ObjID, *itemIndex]
+	excItems containers.ARCache[btrfsprim.ObjID, *itemIndex]
 }
 
 // NewRebuiltForrest returns a new RebuiltForrest instance.  All of
@@ -86,9 +86,15 @@ func NewRebuiltForrest(
 		cbLookupRoot: cbLookupRoot,
 		cbLookupUUID: cbLookupUUID,
 
-		leafs:    containers.NewLRUCache[btrfsprim.ObjID, map[btrfsvol.LogicalAddr]containers.Set[btrfsvol.LogicalAddr]](textui.Tunable(8)),
-		incItems: containers.NewLRUCache[btrfsprim.ObjID, *itemIndex](textui.Tunable(8)),
-		excItems: containers.NewLRUCache[btrfsprim.ObjID, *itemIndex](textui.Tunable(8)),
+		leafs: containers.ARCache[btrfsprim.ObjID, map[btrfsvol.LogicalAddr]containers.Set[btrfsvol.LogicalAddr]]{
+			MaxLen: textui.Tunable(8),
+		},
+		incItems: containers.ARCache[btrfsprim.ObjID, *itemIndex]{
+			MaxLen: textui.Tunable(8),
+		},
+		excItems: containers.ARCache[btrfsprim.ObjID, *itemIndex]{
+			MaxLen: textui.Tunable(8),
+		},
 	}
 }
 
diff --git a/lib/btrfsprogs/btrfsinspect/rebuildnodes/btrees/tree.go b/lib/btrfsprogs/btrfsinspect/rebuildnodes/btrees/tree.go
index 66cb0fa..c9d0fa4 100644
--- a/lib/btrfsprogs/btrfsinspect/rebuildnodes/btrees/tree.go
+++ b/lib/btrfsprogs/btrfsinspect/rebuildnodes/btrees/tree.go
@@ -49,7 +49,7 @@ type RebuiltTree struct {
 // leafToRoots returns all leafs (lvl=0) in the filesystem that pass
 // .isOwnerOK, whether or not they're in the tree.
 func (tree *RebuiltTree) leafToRoots(ctx context.Context) map[btrfsvol.LogicalAddr]containers.Set[btrfsvol.LogicalAddr] {
-	return tree.forrest.leafs.GetOrElse(tree.ID, func() map[btrfsvol.LogicalAddr]containers.Set[btrfsvol.LogicalAddr] {
+	return containers.LoadOrElse[btrfsprim.ObjID, map[btrfsvol.LogicalAddr]containers.Set[btrfsvol.LogicalAddr]](&tree.forrest.leafs, tree.ID, func(btrfsprim.ObjID) map[btrfsvol.LogicalAddr]containers.Set[btrfsvol.LogicalAddr] {
 		ctx = dlog.WithField(ctx, "btrfsinspect.rebuild-nodes.rebuild.index-nodes", fmt.Sprintf("tree=%v", tree.ID))
 
 		nodeToRoots := make(map[btrfsvol.LogicalAddr]containers.Set[btrfsvol.LogicalAddr])
@@ -139,7 +139,7 @@ func (tree *RebuiltTree) isOwnerOK(owner btrfsprim.ObjID, gen btrfsprim.Generati
 // RebuiltTree's internal map!
 func (tree *RebuiltTree) Items(ctx context.Context) *containers.SortedMap[btrfsprim.Key, keyio.ItemPtr] {
 	ctx = dlog.WithField(ctx, "btrfsinspect.rebuild-nodes.rebuild.index-inc-items", fmt.Sprintf("tree=%v", tree.ID))
-	return tree.items(ctx, tree.forrest.incItems, tree.Roots.HasAny)
+	return tree.items(ctx, &tree.forrest.incItems, tree.Roots.HasAny)
 }
 
 // PotentialItems returns a map of items that could be added to this
@@ -149,7 +149,7 @@ func (tree *RebuiltTree) Items(ctx context.Context) *containers.SortedMap[btrfsp
 // RebuiltTree's internal map!
 func (tree *RebuiltTree) PotentialItems(ctx context.Context) *containers.SortedMap[btrfsprim.Key, keyio.ItemPtr] {
 	ctx = dlog.WithField(ctx, "btrfsinspect.rebuild-nodes.rebuild.index-exc-items", fmt.Sprintf("tree=%v", tree.ID))
-	return tree.items(ctx, tree.forrest.excItems,
+	return tree.items(ctx, &tree.forrest.excItems,
 		func(roots containers.Set[btrfsvol.LogicalAddr]) bool {
 			return !tree.Roots.HasAny(roots)
 		})
@@ -168,13 +168,13 @@ func (s itemStats) String() string {
 		s.Leafs, s.NumItems, s.NumDups)
 }
 
-func (tree *RebuiltTree) items(ctx context.Context, cache *containers.LRUCache[btrfsprim.ObjID, *itemIndex],
+func (tree *RebuiltTree) items(ctx context.Context, cache containers.Map[btrfsprim.ObjID, *itemIndex],
 	leafFn func(roots containers.Set[btrfsvol.LogicalAddr]) bool,
 ) *containers.SortedMap[btrfsprim.Key, keyio.ItemPtr] {
 	tree.mu.RLock()
 	defer tree.mu.RUnlock()
 
-	return cache.GetOrElse(tree.ID, func() *itemIndex {
+	return containers.LoadOrElse(cache, tree.ID, func(btrfsprim.ObjID) *itemIndex {
 		var leafs []btrfsvol.LogicalAddr
 		for leaf, roots := range tree.leafToRoots(ctx) {
 			if leafFn(roots) {
@@ -298,8 +298,8 @@ func (tree *RebuiltTree) AddRoot(ctx context.Context, rootNode btrfsvol.LogicalA
 	progressWriter.Done()
 
 	tree.Roots.Insert(rootNode)
-	tree.forrest.incItems.Remove(tree.ID) // force re-gen
-	tree.forrest.excItems.Remove(tree.ID) // force re-gen
+	tree.forrest.incItems.Delete(tree.ID) // force re-gen
+	tree.forrest.excItems.Delete(tree.ID) // force re-gen
 
 	if (tree.ID == btrfsprim.ROOT_TREE_OBJECTID || tree.ID == btrfsprim.UUID_TREE_OBJECTID) && stats.AddedItems > 0 {
 		tree.forrest.trees.Range(func(otherTreeID btrfsprim.ObjID, otherTree *RebuiltTree) bool {
diff --git a/lib/btrfsprogs/btrfsinspect/rebuildnodes/graph/graph.go b/lib/btrfsprogs/btrfsinspect/rebuildnodes/graph/graph.go
index cf86d74..c04fec0 100644
--- a/lib/btrfsprogs/btrfsinspect/rebuildnodes/graph/graph.go
+++ b/lib/btrfsprogs/btrfsinspect/rebuildnodes/graph/graph.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
 
@@ -151,7 +151,7 @@ func (g Graph) InsertNode(nodeRef *diskio.Ref[btrfsvol.LogicalAddr, btrfstree.No
 	if nodeRef.Data.Head.Level == 0 {
 		cnt := 0
 		for _, item := range nodeRef.Data.BodyLeaf {
-			if _, ok := item.Body.(btrfsitem.Root); ok {
+			if _, ok := item.Body.(*btrfsitem.Root); ok {
 				cnt++
 			}
 		}
@@ -161,7 +161,7 @@ func (g Graph) InsertNode(nodeRef *diskio.Ref[btrfsvol.LogicalAddr, btrfstree.No
 		g.Nodes[nodeRef.Addr] = nodeData
 		for i, item := range nodeRef.Data.BodyLeaf {
 			keys[i] = item.Key
-			if itemBody, ok := item.Body.(btrfsitem.Root); ok {
+			if itemBody, ok := item.Body.(*btrfsitem.Root); ok {
 				kps = append(kps, Edge{
 					FromRoot:     nodeRef.Addr,
 					FromItem:     i,
diff --git a/lib/btrfsprogs/btrfsinspect/rebuildnodes/keyio/keyio.go b/lib/btrfsprogs/btrfsinspect/rebuildnodes/keyio/keyio.go
index 64a9828..b4ab645 100644
--- a/lib/btrfsprogs/btrfsinspect/rebuildnodes/keyio/keyio.go
+++ b/lib/btrfsprogs/btrfsinspect/rebuildnodes/keyio/keyio.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
 
@@ -48,7 +48,7 @@ type Handle struct {
 	Names map[ItemPtr][]byte      // DIR_INDEX
 	Sizes map[ItemPtr]SizeAndErr  // EXTENT_CSUM and EXTENT_DATA
 
-	cache *containers.LRUCache[btrfsvol.LogicalAddr, *diskio.Ref[btrfsvol.LogicalAddr, btrfstree.Node]]
+	cache containers.ARCache[btrfsvol.LogicalAddr, *diskio.Ref[btrfsvol.LogicalAddr, btrfstree.Node]]
 }
 
 func NewHandle(file diskio.File[btrfsvol.LogicalAddr], sb btrfstree.Superblock) *Handle {
@@ -60,7 +60,12 @@ func NewHandle(file diskio.File[btrfsvol.LogicalAddr], sb btrfstree.Superblock)
 		Names: make(map[ItemPtr][]byte),
 		Sizes: make(map[ItemPtr]SizeAndErr),
 
-		cache: containers.NewLRUCache[btrfsvol.LogicalAddr, *diskio.Ref[btrfsvol.LogicalAddr, btrfstree.Node]](textui.Tunable(8)),
+		cache: containers.ARCache[btrfsvol.LogicalAddr, *diskio.Ref[btrfsvol.LogicalAddr, btrfstree.Node]]{
+			MaxLen: textui.Tunable(8),
+			OnRemove: func(_ btrfsvol.LogicalAddr, nodeRef *diskio.Ref[btrfsvol.LogicalAddr, btrfstree.Node]) {
+				btrfstree.FreeNodeRef(nodeRef)
+			},
+		},
 	}
 }
 
@@ -71,27 +76,27 @@ func (o *Handle) InsertNode(nodeRef *diskio.Ref[btrfsvol.LogicalAddr, btrfstree.
 			Idx:  i,
 		}
 		switch itemBody := item.Body.(type) {
-		case btrfsitem.Inode:
+		case *btrfsitem.Inode:
 			o.Flags[ptr] = FlagsAndErr{
 				NoDataSum: itemBody.Flags.Has(btrfsitem.INODE_NODATASUM),
 				Err:       nil,
 			}
-		case btrfsitem.DirEntry:
+		case *btrfsitem.DirEntry:
 			if item.Key.ItemType == btrfsprim.DIR_INDEX_KEY {
 				o.Names[ptr] = append([]byte(nil), itemBody.Name...)
 			}
-		case btrfsitem.ExtentCSum:
+		case *btrfsitem.ExtentCSum:
 			o.Sizes[ptr] = SizeAndErr{
 				Size: uint64(itemBody.Size()),
 				Err:  nil,
 			}
-		case btrfsitem.FileExtent:
+		case *btrfsitem.FileExtent:
 			size, err := itemBody.Size()
 			o.Sizes[ptr] = SizeAndErr{
 				Size: uint64(size),
 				Err:  err,
 			}
-		case btrfsitem.Error:
+		case *btrfsitem.Error:
 			switch item.Key.ItemType {
 			case btrfsprim.INODE_ITEM_KEY:
 				o.Flags[ptr] = FlagsAndErr{
@@ -113,7 +118,7 @@ func (o *Handle) SetGraph(graph graph.Graph) {
 }
 
 func (o *Handle) readNode(ctx context.Context, laddr btrfsvol.LogicalAddr) *diskio.Ref[btrfsvol.LogicalAddr, btrfstree.Node] {
-	if cached, ok := o.cache.Get(laddr); ok {
+	if cached, ok := o.cache.Load(laddr); ok {
 		dlog.Tracef(ctx, "cache-hit node@%v", laddr)
 		return cached
 	}
@@ -142,7 +147,7 @@ func (o *Handle) readNode(ctx context.Context, laddr btrfsvol.LogicalAddr) *disk
 		panic(fmt.Errorf("should not happen: i/o error: %w", err))
 	}
 
-	o.cache.Add(laddr, ref)
+	o.cache.Store(laddr, ref)
 
 	return ref
 }
diff --git a/lib/btrfsprogs/btrfsinspect/rebuildnodes/rebuild.go b/lib/btrfsprogs/btrfsinspect/rebuildnodes/rebuild.go
index bd29278..624441f 100644
--- a/lib/btrfsprogs/btrfsinspect/rebuildnodes/rebuild.go
+++ b/lib/btrfsprogs/btrfsinspect/rebuildnodes/rebuild.go
@@ -290,9 +290,9 @@ func (o *rebuilder) cbLookupRoot(ctx context.Context, tree btrfsprim.ObjID) (off
 		o.ioErr(ctx, fmt.Errorf("could not read previously read item: %v", key))
 	}
 	switch itemBody := itemBody.(type) {
-	case btrfsitem.Root:
-		return btrfsprim.Generation(key.Offset), itemBody, true
-	case btrfsitem.Error:
+	case *btrfsitem.Root:
+		return btrfsprim.Generation(key.Offset), *itemBody, true
+	case *btrfsitem.Error:
 		o.fsErr(ctx, fmt.Errorf("error decoding item: %v: %w", key, itemBody.Err))
 		return 0, btrfsitem.Root{}, false
 	default:
@@ -315,9 +315,9 @@ func (o *rebuilder) cbLookupUUID(ctx context.Context, uuid btrfsprim.UUID) (id b
 		o.ioErr(ctx, fmt.Errorf("could not read previously read item: %v", key))
 	}
 	switch itemBody := itemBody.(type) {
-	case btrfsitem.UUIDMap:
+	case *btrfsitem.UUIDMap:
 		return itemBody.ObjID, true
-	case btrfsitem.Error:
+	case *btrfsitem.Error:
 		o.fsErr(ctx, fmt.Errorf("error decoding item: %v: %w", key, itemBody.Err))
 		return 0, false
 	default:
diff --git a/lib/btrfsprogs/btrfsinspect/rebuildnodes/rebuild_graph.go b/lib/btrfsprogs/btrfsinspect/rebuildnodes/rebuild_graph.go
index 9e40465..710030c 100644
--- a/lib/btrfsprogs/btrfsinspect/rebuildnodes/rebuild_graph.go
+++ b/lib/btrfsprogs/btrfsinspect/rebuildnodes/rebuild_graph.go
@@ -50,7 +50,7 @@ func handleItem(o rebuildCallbacks, ctx context.Context, treeID btrfsprim.ObjID,
 	// https://btrfs.wiki.kernel.org/index.php/File:References.png (from the page
 	// https://btrfs.wiki.kernel.org/index.php/Data_Structures )
 	switch body := item.Body.(type) {
-	case btrfsitem.BlockGroup:
+	case *btrfsitem.BlockGroup:
 		o.want(ctx, "Chunk",
 			btrfsprim.CHUNK_TREE_OBJECTID,
 			body.ChunkObjectID,
@@ -60,22 +60,22 @@ func handleItem(o rebuildCallbacks, ctx context.Context, treeID btrfsprim.ObjID,
 			item.Key.ObjectID,
 			btrfsitem.FREE_SPACE_INFO_KEY,
 			item.Key.Offset)
-	case btrfsitem.Chunk:
+	case *btrfsitem.Chunk:
 		o.want(ctx, "owning Root",
 			btrfsprim.ROOT_TREE_OBJECTID,
 			body.Head.Owner,
 			btrfsitem.ROOT_ITEM_KEY)
-	case btrfsitem.Dev:
+	case *btrfsitem.Dev:
 		// nothing
-	case btrfsitem.DevExtent:
+	case *btrfsitem.DevExtent:
 		o.wantOff(ctx, "Chunk",
 			body.ChunkTree,
 			body.ChunkObjectID,
 			btrfsitem.CHUNK_ITEM_KEY,
 			uint64(body.ChunkOffset))
-	case btrfsitem.DevStats:
+	case *btrfsitem.DevStats:
 		// nothing
-	case btrfsitem.DirEntry:
+	case *btrfsitem.DirEntry:
 		// containing-directory
 		o.wantOff(ctx, "containing dir inode",
 			treeID,
@@ -126,9 +126,9 @@ func handleItem(o rebuildCallbacks, ctx context.Context, treeID btrfsprim.ObjID,
 				o.fsErr(ctx, fmt.Errorf("DirEntry: unexpected .Location.ItemType=%v", body.Location.ItemType))
 			}
 		}
-	case btrfsitem.Empty:
+	case *btrfsitem.Empty:
 		// nothing
-	case btrfsitem.Extent:
+	case *btrfsitem.Extent:
 		// if body.Head.Flags.Has(btrfsitem.EXTENT_FLAG_TREE_BLOCK) {
 		// 	// Supposedly this flag indicates that
 		// 	// body.Info.Key identifies a node by the
@@ -140,7 +140,7 @@ func handleItem(o rebuildCallbacks, ctx context.Context, treeID btrfsprim.ObjID,
 			switch refBody := ref.Body.(type) {
 			case nil:
 				// nothing
-			case btrfsitem.ExtentDataRef:
+			case *btrfsitem.ExtentDataRef:
 				o.wantOff(ctx, "referencing Inode",
 					refBody.Root,
 					refBody.ObjectID,
@@ -151,7 +151,7 @@ func handleItem(o rebuildCallbacks, ctx context.Context, treeID btrfsprim.ObjID,
 					refBody.ObjectID,
 					btrfsitem.EXTENT_DATA_KEY,
 					uint64(refBody.Offset))
-			case btrfsitem.SharedDataRef:
+			case *btrfsitem.SharedDataRef:
 				// nothing
 			default:
 				// This is a panic because the item decoder should not emit a new
@@ -159,9 +159,9 @@ func handleItem(o rebuildCallbacks, ctx context.Context, treeID btrfsprim.ObjID,
 				panic(fmt.Errorf("should not happen: Extent: unexpected .Refs[%d].Body type %T", i, refBody))
 			}
 		}
-	case btrfsitem.ExtentCSum:
+	case *btrfsitem.ExtentCSum:
 		// nothing
-	case btrfsitem.ExtentDataRef:
+	case *btrfsitem.ExtentDataRef:
 		o.want(ctx, "Extent being referenced",
 			btrfsprim.EXTENT_TREE_OBJECTID,
 			item.Key.ObjectID,
@@ -176,7 +176,7 @@ func handleItem(o rebuildCallbacks, ctx context.Context, treeID btrfsprim.ObjID,
 			body.ObjectID,
 			btrfsitem.EXTENT_DATA_KEY,
 			uint64(body.Offset))
-	case btrfsitem.FileExtent:
+	case *btrfsitem.FileExtent:
 		o.wantOff(ctx, "containing Inode",
 			treeID,
 			item.Key.ObjectID,
@@ -194,19 +194,19 @@ func handleItem(o rebuildCallbacks, ctx context.Context, treeID btrfsprim.ObjID,
 		default:
 			o.fsErr(ctx, fmt.Errorf("FileExtent: unexpected body.Type=%v", body.Type))
 		}
-	case btrfsitem.FreeSpaceBitmap:
+	case *btrfsitem.FreeSpaceBitmap:
 		o.wantOff(ctx, "FreeSpaceInfo",
 			treeID,
 			item.Key.ObjectID,
 			btrfsitem.FREE_SPACE_INFO_KEY,
 			item.Key.Offset)
-	case btrfsitem.FreeSpaceHeader:
+	case *btrfsitem.FreeSpaceHeader:
 		o.wantOff(ctx, ".Location",
 			treeID,
 			body.Location.ObjectID,
 			body.Location.ItemType,
 			body.Location.Offset)
-	case btrfsitem.FreeSpaceInfo:
+	case *btrfsitem.FreeSpaceInfo:
 		if body.Flags.Has(btrfsitem.FREE_SPACE_USING_BITMAPS) {
 			o.wantOff(ctx, "FreeSpaceBitmap",
 				treeID,
@@ -214,7 +214,7 @@ func handleItem(o rebuildCallbacks, ctx context.Context, treeID btrfsprim.ObjID,
 				btrfsitem.FREE_SPACE_BITMAP_KEY,
 				item.Key.Offset)
 		}
-	case btrfsitem.Inode:
+	case *btrfsitem.Inode:
 		o.want(ctx, "backrefs",
 			treeID, // TODO: validate the number of these against body.NLink
 			item.Key.ObjectID,
@@ -227,7 +227,7 @@ func handleItem(o rebuildCallbacks, ctx context.Context, treeID btrfsprim.ObjID,
 				body.BlockGroup,
 				btrfsitem.BLOCK_GROUP_ITEM_KEY)
 		}
-	case btrfsitem.InodeRefs:
+	case *btrfsitem.InodeRefs:
 		o.wantOff(ctx, "child Inode",
 			treeID,
 			item.Key.ObjectID,
@@ -238,7 +238,7 @@ func handleItem(o rebuildCallbacks, ctx context.Context, treeID btrfsprim.ObjID,
 			btrfsprim.ObjID(item.Key.Offset),
 			btrfsitem.INODE_ITEM_KEY,
 			0)
-		for _, ref := range body {
+		for _, ref := range body.Refs {
 			o.wantOff(ctx, "DIR_ITEM",
 				treeID,
 				btrfsprim.ObjID(item.Key.Offset),
@@ -250,12 +250,12 @@ func handleItem(o rebuildCallbacks, ctx context.Context, treeID btrfsprim.ObjID,
 				btrfsitem.DIR_INDEX_KEY,
 				uint64(ref.Index))
 		}
-	case btrfsitem.Metadata:
+	case *btrfsitem.Metadata:
 		for i, ref := range body.Refs {
 			switch refBody := ref.Body.(type) {
 			case nil:
 				// nothing
-			case btrfsitem.ExtentDataRef:
+			case *btrfsitem.ExtentDataRef:
 				o.wantOff(ctx, "referencing INode",
 					refBody.Root,
 					refBody.ObjectID,
@@ -266,7 +266,7 @@ func handleItem(o rebuildCallbacks, ctx context.Context, treeID btrfsprim.ObjID,
 					refBody.ObjectID,
 					btrfsitem.EXTENT_DATA_KEY,
 					uint64(refBody.Offset))
-			case btrfsitem.SharedDataRef:
+			case *btrfsitem.SharedDataRef:
 				// nothing
 			default:
 				// This is a panic because the item decoder should not emit a new
@@ -274,7 +274,7 @@ func handleItem(o rebuildCallbacks, ctx context.Context, treeID btrfsprim.ObjID,
 				panic(fmt.Errorf("should not happen: Metadata: unexpected .Refs[%d].Body type %T", i, refBody))
 			}
 		}
-	case btrfsitem.Root:
+	case *btrfsitem.Root:
 		if body.RootDirID != 0 {
 			o.wantOff(ctx, "root directory",
 				item.Key.ObjectID,
@@ -298,7 +298,7 @@ func handleItem(o rebuildCallbacks, ctx context.Context, treeID btrfsprim.ObjID,
 				key.ItemType,
 				key.Offset)
 		}
-	case btrfsitem.RootRef:
+	case *btrfsitem.RootRef:
 		var otherType btrfsprim.ItemType
 		var parent, child btrfsprim.ObjID
 		switch item.Key.ItemType {
@@ -347,17 +347,17 @@ func handleItem(o rebuildCallbacks, ctx context.Context, treeID btrfsprim.ObjID,
 			treeID,
 			child,
 			btrfsitem.ROOT_ITEM_KEY)
-	case btrfsitem.SharedDataRef:
+	case *btrfsitem.SharedDataRef:
 		o.want(ctx, "Extent",
 			btrfsprim.EXTENT_TREE_OBJECTID,
 			item.Key.ObjectID,
 			btrfsitem.EXTENT_ITEM_KEY)
-	case btrfsitem.UUIDMap:
+	case *btrfsitem.UUIDMap:
 		o.want(ctx, "subvolume Root",
 			btrfsprim.ROOT_TREE_OBJECTID,
 			body.ObjID,
 			btrfsitem.ROOT_ITEM_KEY)
-	case btrfsitem.Error:
+	case *btrfsitem.Error:
 		o.fsErr(ctx, fmt.Errorf("error decoding item: %w", body.Err))
 	default:
 		// This is a panic because the item decoder should not emit new types without this
diff --git a/lib/btrfsprogs/btrfsinspect/rebuildnodes/scan.go b/lib/btrfsprogs/btrfsinspect/rebuildnodes/scan.go
index 7e19802..632ed70 100644
--- a/lib/btrfsprogs/btrfsinspect/rebuildnodes/scan.go
+++ b/lib/btrfsprogs/btrfsinspect/rebuildnodes/scan.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
 
@@ -48,12 +48,15 @@ func ScanDevices(ctx context.Context, fs *btrfs.FS, scanResults btrfsinspect.Sca
 				LAddr: containers.Optional[btrfsvol.LogicalAddr]{OK: true, Val: laddr},
 			})
 			if err != nil {
+				btrfstree.FreeNodeRef(nodeRef)
 				return btrfstree.Superblock{}, graph.Graph{}, nil, err
 			}
 
 			nodeGraph.InsertNode(nodeRef)
 			keyIO.InsertNode(nodeRef)
 
+			btrfstree.FreeNodeRef(nodeRef)
+
 			stats.N++
 			progressWriter.Set(stats)
 		}