From ec31481b46fb772dfe2e977ef37fc0ace39fad8a Mon Sep 17 00:00:00 2001
From: Luke Shumaker <lukeshu@lukeshu.com>
Date: Thu, 22 Dec 2022 16:30:27 -0700
Subject: rebuildnodes/btrees: Try to handle duplicate keys by generation

---
 .../rebuildnodes/btrees/rebuilt_btrees.go          | 56 ++++++++++++++--------
 1 file changed, 37 insertions(+), 19 deletions(-)

(limited to 'lib/btrfsprogs/btrfsinspect')

diff --git a/lib/btrfsprogs/btrfsinspect/rebuildnodes/btrees/rebuilt_btrees.go b/lib/btrfsprogs/btrfsinspect/rebuildnodes/btrees/rebuilt_btrees.go
index 23e974e..cbe7df1 100644
--- a/lib/btrfsprogs/btrfsinspect/rebuildnodes/btrees/rebuilt_btrees.go
+++ b/lib/btrfsprogs/btrfsinspect/rebuildnodes/btrees/rebuilt_btrees.go
@@ -136,17 +136,18 @@ type rootStats struct {
 	TreeID   btrfsprim.ObjID
 	RootNode btrfsvol.LogicalAddr
 
-	DoneLeafs  int
-	TotalLeafs int
-	AddedItems int
+	DoneLeafs     int
+	TotalLeafs    int
+	AddedItems    int
+	ReplacedItems int
 }
 
 func (s rootStats) String() string {
-	return fmt.Sprintf("tree %v: adding root node@%v: %v%% (%v/%v) (added %v items)",
+	return fmt.Sprintf("tree %v: adding root node@%v: %v%% (%v/%v) (added %v items, replaced %v items)",
 		s.TreeID, s.RootNode,
 		int(100*float64(s.DoneLeafs)/float64(s.TotalLeafs)),
 		s.DoneLeafs, s.TotalLeafs,
-		s.AddedItems)
+		s.AddedItems, s.ReplacedItems)
 }
 
 // AddRoot adds an additional root node to an existing tree.  It is
@@ -161,13 +162,15 @@ func (ts *RebuiltTrees) AddRoot(ctx context.Context, treeID btrfsprim.ObjID, roo
 
 	progressWriter := textui.NewProgress[rootStats](ctx, dlog.LogLevelInfo, 1*time.Second)
 	numAdded := 0
+	numReplaced := 0
 	progress := func(done int) {
 		progressWriter.Set(rootStats{
-			TreeID:     treeID,
-			RootNode:   rootNode,
-			DoneLeafs:  done,
-			TotalLeafs: len(tree.leafToRoots),
-			AddedItems: numAdded,
+			TreeID:        treeID,
+			RootNode:      rootNode,
+			DoneLeafs:     done,
+			TotalLeafs:    len(tree.leafToRoots),
+			AddedItems:    numAdded,
+			ReplacedItems: numReplaced,
 		})
 	}
 	for i, leaf := range maps.SortedKeys(tree.leafToRoots) {
@@ -177,17 +180,32 @@ func (ts *RebuiltTrees) AddRoot(ctx context.Context, treeID btrfsprim.ObjID, roo
 			continue
 		}
 		for j, item := range ts.keyIO.ReadNode(leaf).Data.BodyLeaf {
-			if _, exists := tree.Items.Load(item.Key); exists {
-				// 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
-				// and force me to figure out how to handle it.
-				panic(fmt.Errorf("dup key=%v in tree=%v", item.Key, treeID))
-			}
-			tree.Items.Store(item.Key, keyio.ItemPtr{
+			newPtr := keyio.ItemPtr{
 				Node: leaf,
 				Idx:  j,
-			})
-			numAdded++
+			}
+			if oldPtr, exists := tree.Items.Load(item.Key); !exists {
+				tree.Items.Store(item.Key, newPtr)
+				numAdded++
+			} else {
+				oldGen := ts.graph.Nodes[oldPtr.Node].Generation
+				newGen := ts.graph.Nodes[newPtr.Node].Generation
+				switch {
+				case oldGen < newGen:
+					tree.Items.Store(item.Key, newPtr)
+					numReplaced++
+				case oldGen > newGen:
+					// keep the old one
+				case oldGen == newGen:
+					// 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
+					// and force me to figure out how to handle it.
+					panic(fmt.Errorf("dup key=%v in tree=%v: old=%v=%#v ; new=%v=%#v",
+						item.Key, treeID,
+						oldPtr, ts.graph.Nodes[oldPtr.Node],
+						newPtr, ts.graph.Nodes[newPtr.Node]))
+				}
+			}
 			ts.cbAddedItem(ctx, treeID, item.Key)
 			progress(i)
 		}
-- 
cgit v1.2.3-2-g168b