From 75333b3f1dcc0ac23caa9137d9f1fcaff57c4067 Mon Sep 17 00:00:00 2001
From: Luke Shumaker <lukeshu@lukeshu.com>
Date: Sun, 12 Jun 2022 17:21:17 -0600
Subject: work on pass2

---
 cmd/btrfs-fsck/pass2.go  | 41 ++++++++++++++++++++++++++++++++++++-----
 pkg/btrfs/types_btree.go | 35 +++++++++++++++++++++++++++++------
 2 files changed, 65 insertions(+), 11 deletions(-)

diff --git a/cmd/btrfs-fsck/pass2.go b/cmd/btrfs-fsck/pass2.go
index 46fa40e..b38fbcc 100644
--- a/cmd/btrfs-fsck/pass2.go
+++ b/cmd/btrfs-fsck/pass2.go
@@ -2,6 +2,8 @@ package main
 
 import (
 	"fmt"
+	iofs "io/fs"
+	"sort"
 
 	"lukeshu.com/btrfs-tools/pkg/btrfs"
 	"lukeshu.com/btrfs-tools/pkg/btrfs/btrfsitem"
@@ -30,7 +32,7 @@ func walkFS(fs *btrfs.FS, cbs btrfs.WalkTreeHandler, errCb func(error)) {
 					Name string
 					Root btrfs.LogicalAddr
 				}{
-					Name: fmt.Sprintf("found tree %v at [%v %v]",
+					Name: fmt.Sprintf("tree %v (via %v %v)",
 						item.Head.Key.ObjectID.Format(0), treeName, path),
 					Root: root.ByteNr,
 				})
@@ -98,15 +100,44 @@ func pass2(fs *btrfs.FS, foundNodes map[btrfs.LogicalAddr]struct{}) {
 			return nil
 		},
 	}, func(err error) {
-		fmt.Printf("Pass 2: error: %v\n", err)
+		fmt.Printf("Pass 2: walk FS: error: %v\n", err)
 	})
 
-	orphanedNodes := make(map[btrfs.LogicalAddr]struct{})
+	orphanedNodes := make(map[btrfs.LogicalAddr]int)
 	for foundNode := range foundNodes {
 		if _, visited := visitedNodes[foundNode]; !visited {
-			orphanedNodes[foundNode] = struct{}{}
+			orphanedNodes[foundNode] = 0
 		}
 	}
 
-	//fmt.Printf("Pass 2: orphanedNodes=%#v\n", orphanedNodes)
+	for nodeAddr := range orphanedNodes {
+		if err := fs.WalkTree(nodeAddr, btrfs.WalkTreeHandler{
+			Node: func(path btrfs.WalkTreePath, node *util.Ref[btrfs.LogicalAddr, btrfs.Node], err error) error {
+				nodeAddr := path[len(path)-1].NodeAddr
+				orphanedNodes[nodeAddr] = orphanedNodes[nodeAddr] + 1
+				visitCnt := orphanedNodes[nodeAddr]
+				if visitCnt > 1 {
+					return iofs.SkipDir
+				}
+				return nil
+			},
+		}); err != nil {
+			fmt.Printf("Pass 2: walk orphans: error: %v\n", err)
+		}
+	}
+	var orphanedRoots []btrfs.LogicalAddr
+	for node, cnt := range orphanedNodes {
+		switch cnt {
+		case 0:
+			panic("x")
+		case 1:
+			orphanedRoots = append(orphanedRoots, node)
+		}
+	}
+	sort.Slice(orphanedRoots, func(i, j int) bool {
+		return orphanedRoots[i] < orphanedRoots[j]
+	})
+	for _, node := range orphanedRoots {
+		fmt.Printf("Pass 2: orphaned root: %v\n", node)
+	}
 }
diff --git a/pkg/btrfs/types_btree.go b/pkg/btrfs/types_btree.go
index 10babfd..99371d2 100644
--- a/pkg/btrfs/types_btree.go
+++ b/pkg/btrfs/types_btree.go
@@ -4,7 +4,9 @@ import (
 	"encoding/binary"
 	"errors"
 	"fmt"
+	"io"
 	iofs "io/fs"
+	"math"
 	"strings"
 
 	"lukeshu.com/btrfs-tools/pkg/binstruct"
@@ -391,6 +393,17 @@ type WalkTreePathElem struct {
 	// points at, or 0 if this is a leaf item and nothing is
 	// being pointed at.
 	NodeAddr LogicalAddr
+	// NodeLevel is the expected or actual level of the node at
+	// NodeAddr, or 255 if there is no knowledge of the level.
+	NodeLevel uint8
+}
+
+func (elem WalkTreePathElem) writeNodeTo(w io.Writer) {
+	if elem.NodeLevel != math.MaxUint8 {
+		fmt.Fprintf(w, "node:%d@%v", elem.NodeLevel, elem.NodeAddr)
+	} else {
+		fmt.Fprintf(w, "node@%v", elem.NodeAddr)
+	}
 }
 
 // - The first element will always have an ItemIdx of -1.
@@ -404,11 +417,12 @@ func (path WalkTreePath) String() string {
 		return "(empty-path)"
 	}
 	var ret strings.Builder
-	fmt.Fprintf(&ret, "node@%v", path[0].NodeAddr)
+	path[0].writeNodeTo(&ret)
 	for _, elem := range path[1:] {
 		fmt.Fprintf(&ret, "[%v]", elem.ItemIdx)
 		if elem.NodeAddr != 0 {
-			fmt.Fprintf(&ret, "->node@%v", elem.NodeAddr)
+			ret.WriteString("->")
+			elem.writeNodeTo(&ret)
 		}
 	}
 	return ret.String()
@@ -442,8 +456,9 @@ type WalkTreeHandler struct {
 func (fs *FS) WalkTree(nodeAddr LogicalAddr, cbs WalkTreeHandler) error {
 	path := WalkTreePath{
 		WalkTreePathElem{
-			ItemIdx:  -1,
-			NodeAddr: nodeAddr,
+			ItemIdx:   -1,
+			NodeAddr:  nodeAddr,
+			NodeLevel: math.MaxUint8,
 		},
 	}
 	return fs.walkTree(path, cbs)
@@ -463,6 +478,13 @@ func (fs *FS) walkTree(path WalkTreePath, cbs WalkTreeHandler) error {
 		}
 	}
 	node, err := fs.ReadNode(path[len(path)-1].NodeAddr)
+	if node != nil {
+		if exp := path[len(path)-1].NodeLevel; exp != math.MaxUint8 && node.Data.Head.Level != exp && err == nil {
+			err = fmt.Errorf("btrfs.FS.WalkTree: node@%v: expected level %v but has level %v",
+				node.Addr, exp, node.Data.Head.Level)
+		}
+		path[len(path)-1].NodeLevel = node.Data.Head.Level
+	}
 	if cbs.Node != nil {
 		err = cbs.Node(path, node, err)
 	}
@@ -475,8 +497,9 @@ func (fs *FS) walkTree(path WalkTreePath, cbs WalkTreeHandler) error {
 	if node != nil {
 		for i, item := range node.Data.BodyInternal {
 			itemPath := append(path, WalkTreePathElem{
-				ItemIdx:  i,
-				NodeAddr: item.BlockPtr,
+				ItemIdx:   i,
+				NodeAddr:  item.BlockPtr,
+				NodeLevel: node.Data.Head.Level - 1,
 			})
 			if cbs.PreKeyPointer != nil {
 				if err := cbs.PreKeyPointer(itemPath, item); err != nil {
-- 
cgit v1.2.3-2-g168b