wip

5 files changed, 169 insertions, 63 deletions

diff --git a/lib/btrfsprogs/btrfsinspect/rebuildnodes/rebuildnodes.go b/lib/btrfsprogs/btrfsinspect/rebuildnodes/rebuildnodes.go
index a9ff24d..173529e 100644
--- a/lib/btrfsprogs/btrfsinspect/rebuildnodes/rebuildnodes.go
+++ b/lib/btrfsprogs/btrfsinspect/rebuildnodes/rebuildnodes.go
@@ -31,7 +31,12 @@ func RebuildNodes(ctx context.Context, fs *btrfs.FS, nodeScanResults btrfsinspec
 		uuidMap: uuidMap,
 	}
 
-	orphanedNodes, rebuiltNodes, err := classifyNodes(ctx, nfs, nodeScanResults)
+	orphanedNodes, badNodes, err := classifyNodes(ctx, nfs, nodeScanResults)
+	if err != nil {
+		return nil, err
+	}
+
+	rebuiltNodes, err := reInitBrokenNodes(ctx, nfs, badNodes)
 	if err != nil {
 		return nil, err
 	}
@@ -138,10 +143,3 @@ func getChunkTreeUUID(ctx context.Context, fs _FS) (btrfsprim.UUID, bool) {
 	})
 	return ret, retOK
 }
-
-type RebuiltNode struct {
-	Err            string
-	MinKey, MaxKey btrfsprim.Key
-	InTrees        containers.Set[btrfsprim.ObjID]
-	btrfstree.Node
-}
diff --git a/lib/btrfsprogs/btrfsinspect/rebuildnodes/s2_classify.go b/lib/btrfsprogs/btrfsinspect/rebuildnodes/s2_classify.go
index 9fb5bf5..36e5395 100644
--- a/lib/btrfsprogs/btrfsinspect/rebuildnodes/s2_classify.go
+++ b/lib/btrfsprogs/btrfsinspect/rebuildnodes/s2_classify.go
@@ -7,43 +7,35 @@ package rebuildnodes
 import (
 	"context"
 	"errors"
-	"fmt"
 	iofs "io/fs"
-	"reflect"
 	"strings"
 
 	"github.com/datawire/dlib/dlog"
 
-	"git.lukeshu.com/btrfs-progs-ng/lib/btrfs/btrfsprim"
 	"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/btrfsprogs/btrfsinspect"
 	"git.lukeshu.com/btrfs-progs-ng/lib/btrfsprogs/btrfsutil"
-	"git.lukeshu.com/btrfs-progs-ng/lib/containers"
 	"git.lukeshu.com/btrfs-progs-ng/lib/diskio"
 	"git.lukeshu.com/btrfs-progs-ng/lib/maps"
 )
 
+type badNode struct {
+	Err  string
+	Path btrfstree.TreePath
+}
+
 // classifyNodes returns
 //
 //  1. the set of nodes don't have another node claiming it as a child, and
-//  2. the set of bad-nodes, with reconstructed headers filled in.
+//  2. the list of bad nodes (in no particular order)
 func classifyNodes(ctx context.Context, fs _FS, scanResults btrfsinspect.ScanDevicesResult) (
 	orphanedNodes map[btrfsvol.LogicalAddr]struct{},
-	rebuiltNodes map[btrfsvol.LogicalAddr]*RebuiltNode,
+	badNodes []badNode,
 	err error,
 ) {
 	dlog.Info(ctx, "Walking trees to identify orphan and broken nodes...")
 
-	sb, err := fs.Superblock()
-	if err != nil {
-		return nil, nil, err
-	}
-	chunkTreeUUID, ok := getChunkTreeUUID(ctx, fs)
-	if !ok {
-		return nil, nil, fmt.Errorf("could not look up chunk tree UUID")
-	}
-
 	lastPct := -1
 	total := countNodes(scanResults)
 	visitedNodes := make(map[btrfsvol.LogicalAddr]struct{})
@@ -57,7 +49,6 @@ func classifyNodes(ctx context.Context, fs _FS, scanResults btrfsinspect.ScanDev
 		}
 	}
 
-	rebuiltNodes = make(map[btrfsvol.LogicalAddr]*RebuiltNode)
 	walkHandler := btrfstree.TreeWalkHandler{
 		PreNode: func(path btrfstree.TreePath) error {
 			addr := path.Node(-1).ToNodeAddr
@@ -75,40 +66,10 @@ func classifyNodes(ctx context.Context, fs _FS, scanResults btrfsinspect.ScanDev
 			return nil
 		},
 		BadNode: func(path btrfstree.TreePath, _ *diskio.Ref[btrfsvol.LogicalAddr, btrfstree.Node], err error) error {
-			node := btrfstree.Node{
-				Size:         sb.NodeSize,
-				ChecksumType: sb.ChecksumType,
-				Head: btrfstree.NodeHeader{
-					MetadataUUID:  sb.EffectiveMetadataUUID(),
-					Addr:          path.Node(-1).ToNodeAddr,
-					ChunkTreeUUID: chunkTreeUUID,
-					//Owner:         TBD, // see RebuiltNode.InTrees
-					Generation: path.Node(-1).FromGeneration,
-					Level:      path.Node(-1).ToNodeLevel,
-				},
-			}
-			min, max := spanOfTreePath(fs, path)
-			if other, ok := rebuiltNodes[path.Node(-1).ToNodeAddr]; ok {
-				if !reflect.DeepEqual(other.Node, node) {
-					dlog.Errorf(ctx, "... mismatch: %v != %v", node, other.Node)
-					return err
-				}
-				if min.Cmp(other.MinKey) > 0 { // if min > other.MinKey {
-					other.MinKey = min // take the max of the two
-				}
-				if max.Cmp(other.MaxKey) < 0 { // if max < other.MaxKey {
-					other.MaxKey = max // take the min of the two
-				}
-				other.InTrees.Insert(path.Node(-1).FromTree)
-			} else {
-				rebuiltNodes[path.Node(-1).ToNodeAddr] = &RebuiltNode{
-					Err:     err.Error(),
-					MinKey:  min,
-					MaxKey:  max,
-					InTrees: containers.Set[btrfsprim.ObjID]{path.Node(-1).FromTree: struct{}{}},
-					Node:    node,
-				}
-			}
+			badNodes = append(badNodes, badNode{
+				Err:  err.Error(),
+				Path: path.DeepCopy(),
+			})
 			return err
 		},
 	}
@@ -161,6 +122,6 @@ func classifyNodes(ctx context.Context, fs _FS, scanResults btrfsinspect.ScanDev
 		panic("should not happen")
 	}
 
-	dlog.Infof(ctx, "... identified %d orphaned nodes and re-built %d nodes", len(orphanedNodes), len(rebuiltNodes))
-	return orphanedNodes, rebuiltNodes, nil
+	dlog.Infof(ctx, "... identified %d orphaned nodes and %d bad nodes", len(orphanedNodes), len(badNodes))
+	return orphanedNodes, badNodes, nil
 }
diff --git a/lib/btrfsprogs/btrfsinspect/rebuildnodes/s3_reinit.go b/lib/btrfsprogs/btrfsinspect/rebuildnodes/s3_reinit.go
new file mode 100644
index 0000000..a4b8f0f
--- /dev/null
+++ b/lib/btrfsprogs/btrfsinspect/rebuildnodes/s3_reinit.go
@@ -0,0 +1,137 @@
+// Copyright (C) 2022  Luke Shumaker <lukeshu@lukeshu.com>
+//
+// SPDX-License-Identifier: GPL-2.0-or-later
+
+package rebuildnodes
+
+import (
+	"context"
+	"fmt"
+	"reflect"
+	"sort"
+
+	"github.com/datawire/dlib/dlog"
+
+	"git.lukeshu.com/btrfs-progs-ng/lib/btrfs/btrfsprim"
+	"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/slices"
+)
+
+type RebuiltNode struct {
+	Err            string
+	MinKey, MaxKey btrfsprim.Key
+	InTrees        containers.Set[btrfsprim.ObjID]
+	btrfstree.Node
+}
+
+func (a RebuiltNode) Compat(b RebuiltNode) bool {
+	a.Node.Head.Generation = b.Node.Head.Generation
+	return reflect.DeepEqual(a.Node, b.Node)
+}
+
+func (a RebuiltNode) Merge(b RebuiltNode) (RebuiltNode, error) {
+	if !a.Compat(b) {
+		switch {
+		case a.Node.Head.Generation > b.Node.Head.Generation:
+			return a, nil
+		case a.Node.Head.Generation < b.Node.Head.Generation:
+			return b, nil
+		default:
+			return a, fmt.Errorf("mismatch: %v != %v", a, b)
+		}
+	}
+
+	// take the broadest region
+	if a.MinKey.Cmp(b.MinKey) > 0 { // if a.MinKey > b.MinKey {
+		a.MinKey = b.MinKey // take the min of the two
+	}
+	if a.MaxKey.Cmp(b.MaxKey) < 0 { // if a.MaxKey < b.MaxKey {
+		a.MaxKey = b.MaxKey // take the min of the two
+	}
+
+	// take the highest generation
+	a.Node.Head.Generation = slices.Max(a.Node.Head.Generation, b.Node.Head.Generation)
+
+	// take the union
+	a.InTrees.InsertFrom(b.InTrees)
+
+	return a, nil
+}
+
+func reInitBrokenNodes(ctx context.Context, fs _FS, badNodes []badNode) (map[btrfsvol.LogicalAddr]*RebuiltNode, error) {
+	dlog.Info(ctx, "Re-initializing bad nodes...")
+
+	sb, err := fs.Superblock()
+	if err != nil {
+		return nil, err
+	}
+	chunkTreeUUID, ok := getChunkTreeUUID(ctx, fs)
+	if !ok {
+		return nil, fmt.Errorf("could not look up chunk tree UUID")
+	}
+
+	sort.Slice(badNodes, func(i, j int) bool {
+		iGen := badNodes[i].Path.Node(-1).FromGeneration
+		jGen := badNodes[j].Path.Node(-1).FromGeneration
+		switch {
+		case iGen < jGen:
+			return true
+		case iGen > jGen:
+			return false
+		default:
+			iAddr := badNodes[i].Path.Node(-1).ToNodeAddr
+			jAddr := badNodes[j].Path.Node(-1).ToNodeAddr
+			return iAddr < jAddr
+		}
+	})
+
+	lastPct := -1
+	progress := func(done int) {
+		pct := int(100 * float64(done) / float64(len(badNodes)))
+		if pct != lastPct || done == len(badNodes) {
+			dlog.Infof(ctx, "... %v%% (%v/%v)",
+				pct, done, len(badNodes))
+			lastPct = pct
+		}
+	}
+
+	rebuiltNodes := make(map[btrfsvol.LogicalAddr]*RebuiltNode)
+	for i, badNode := range badNodes {
+		progress(i)
+		path := badNode.Path
+
+		min, max := spanOfTreePath(fs, path)
+		node := RebuiltNode{
+			Err:     err.Error(),
+			MinKey:  min,
+			MaxKey:  max,
+			InTrees: containers.Set[btrfsprim.ObjID]{path.Node(-1).FromTree: struct{}{}},
+			Node: btrfstree.Node{
+				Size:         sb.NodeSize,
+				ChecksumType: sb.ChecksumType,
+				Head: btrfstree.NodeHeader{
+					MetadataUUID:  sb.EffectiveMetadataUUID(),
+					Addr:          path.Node(-1).ToNodeAddr,
+					ChunkTreeUUID: chunkTreeUUID,
+					//Owner:      TBD, // see RebuiltNode.InTrees
+					Generation: path.Node(-1).FromGeneration,
+					Level:      path.Node(-1).ToNodeLevel,
+				},
+			},
+		}
+		if other, ok := rebuiltNodes[path.Node(-1).ToNodeAddr]; ok {
+			*other, err = other.Merge(node)
+			if err != nil {
+				dlog.Errorf(ctx, "... %v", err)
+			}
+		} else {
+			rebuiltNodes[path.Node(-1).ToNodeAddr] = &node
+		}
+	}
+	progress(len(badNodes))
+
+	dlog.Infof(ctx, "... initialized %d nodes", len(rebuiltNodes))
+	return rebuiltNodes, nil
+}
diff --git a/lib/btrfsprogs/btrfsinspect/rebuildnodes/s3_reattach.go b/lib/btrfsprogs/btrfsinspect/rebuildnodes/s4_reattach.go
index 2b18aca..28bd834 100644
--- a/lib/btrfsprogs/btrfsinspect/rebuildnodes/s3_reattach.go
+++ b/lib/btrfsprogs/btrfsinspect/rebuildnodes/s4_reattach.go
@@ -19,7 +19,7 @@ import (
 )
 
 func reAttachNodes(ctx context.Context, fs _FS, orphanedNodes map[btrfsvol.LogicalAddr]struct{}, rebuiltNodes map[btrfsvol.LogicalAddr]*RebuiltNode) error {
-	dlog.Info(ctx, "Attaching lost+found nodes to rebuilt nodes...")
+	dlog.Info(ctx, "Attaching orphaned nodes to rebuilt nodes...")
 
 	sb, err := fs.Superblock()
 	if err != nil {
@@ -105,6 +105,7 @@ func reAttachNodes(ctx context.Context, fs _FS, orphanedNodes map[btrfsvol.Logic
 				BlockPtr:   foundLAddr,
 				Generation: foundRef.Data.Head.Generation,
 			})
+			parent.Head.Generation = slices.Max(parent.Head.Generation, foundRef.Data.Head.Generation)
 			attached = true
 			numAttached++
 		}
diff --git a/lib/containers/set.go b/lib/containers/set.go
index e20b5be..4e40894 100644
--- a/lib/containers/set.go
+++ b/lib/containers/set.go
@@ -46,14 +46,23 @@ func (o *Set[T]) DecodeJSON(r io.RuneScanner) error {
 }
 
 func (o *Set[T]) Insert(v T) {
-	if o == nil {
+	if *o == nil {
 		*o = Set[T]{}
 	}
 	(*o)[v] = struct{}{}
 }
 
+func (o *Set[T]) InsertFrom(p Set[T]) {
+	if *o == nil {
+		*o = Set[T]{}
+	}
+	for v := range p {
+		(*o)[v] = struct{}{}
+	}
+}
+
 func (o *Set[T]) Delete(v T) {
-	if o == nil {
+	if *o == nil {
 		return
 	}
 	delete(*o, v)