summaryrefslogtreecommitdiff
path: root/lib/btrfsutil
diff options
context:
space:
mode:
Diffstat (limited to 'lib/btrfsutil')
-rw-r--r--lib/btrfsutil/graph.go265
-rw-r--r--lib/btrfsutil/graph_loops.go133
-rw-r--r--lib/btrfsutil/nestedlock.go45
-rw-r--r--lib/btrfsutil/old_rebuilt_forrest.go363
-rw-r--r--lib/btrfsutil/open.go46
-rw-r--r--lib/btrfsutil/print_addrspace.go73
-rw-r--r--lib/btrfsutil/rebuilt_forrest.go208
-rw-r--r--lib/btrfsutil/rebuilt_readitem.go172
-rw-r--r--lib/btrfsutil/rebuilt_tree.go357
-rw-r--r--lib/btrfsutil/skinny_paths.go146
-rw-r--r--lib/btrfsutil/walk.go97
11 files changed, 1905 insertions, 0 deletions
diff --git a/lib/btrfsutil/graph.go b/lib/btrfsutil/graph.go
new file mode 100644
index 0000000..2a97ec8
--- /dev/null
+++ b/lib/btrfsutil/graph.go
@@ -0,0 +1,265 @@
+// Copyright (C) 2022-2023 Luke Shumaker <lukeshu@lukeshu.com>
+//
+// SPDX-License-Identifier: GPL-2.0-or-later
+
+package graph
+
+import (
+ "context"
+ "fmt"
+ "reflect"
+ "time"
+
+ "github.com/datawire/dlib/dlog"
+
+ "git.lukeshu.com/btrfs-progs-ng/lib/btrfs/btrfsitem"
+ "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/diskio"
+ "git.lukeshu.com/btrfs-progs-ng/lib/maps"
+ "git.lukeshu.com/btrfs-progs-ng/lib/slices"
+ "git.lukeshu.com/btrfs-progs-ng/lib/textui"
+)
+
+type Node struct {
+ Level uint8
+ Generation btrfsprim.Generation
+ Owner btrfsprim.ObjID
+ NumItems uint32
+ MinItem btrfsprim.Key
+ MaxItem btrfsprim.Key
+ Items []btrfsprim.Key
+}
+
+func (n Node) String() string {
+ if reflect.ValueOf(n).IsZero() {
+ return "{}"
+ }
+ return fmt.Sprintf(`{lvl:%v, gen:%v, tree:%v, cnt:%v, min:(%v,%v,%v), max:(%v,%v,%v)}`,
+ n.Level, n.Generation, n.Owner, n.NumItems,
+ n.MinItem.ObjectID, n.MinItem.ItemType, n.MinItem.Offset,
+ n.MaxItem.ObjectID, n.MaxItem.ItemType, n.MaxItem.Offset)
+}
+
+type Edge struct {
+ // It is invalid for both 'FromRoot' and 'FromNode' to be
+ // non-zero. If both are zero, then the Edge is from the
+ // superblock.
+ FromRoot btrfsvol.LogicalAddr
+ FromNode btrfsvol.LogicalAddr
+ FromItem int // only valid if one of FromRoot or FromNode is non-zero
+
+ FromTree btrfsprim.ObjID
+
+ ToNode btrfsvol.LogicalAddr
+ ToLevel uint8
+ ToKey btrfsprim.Key
+ ToGeneration btrfsprim.Generation
+}
+
+func (kp Edge) String() string {
+ var from string
+ switch {
+ case kp.FromRoot != 0:
+ from = fmt.Sprintf("root@%v[%d]:%v",
+ kp.FromRoot, kp.FromItem, kp.FromTree)
+ case kp.FromNode != 0:
+ from = fmt.Sprintf("{node:%v, tree:%v}[%d]",
+ kp.FromNode, kp.FromTree, kp.FromItem)
+ default:
+ from = fmt.Sprintf("superblock:%v", kp.FromTree)
+ }
+ return fmt.Sprintf(`%s -> {n:%v,l:%v,g:%v,k:(%v,%v,%v)}`,
+ from,
+ kp.ToNode, kp.ToLevel, kp.ToGeneration,
+ kp.ToKey.ObjectID,
+ kp.ToKey.ItemType,
+ kp.ToKey.Offset)
+}
+
+type Graph struct {
+ Nodes map[btrfsvol.LogicalAddr]Node
+ BadNodes map[btrfsvol.LogicalAddr]error
+ EdgesFrom map[btrfsvol.LogicalAddr][]*Edge
+ EdgesTo map[btrfsvol.LogicalAddr][]*Edge
+}
+
+func (g Graph) insertEdge(ptr *Edge) {
+ if ptr.ToNode == 0 {
+ panic("kp.ToNode should not be zero")
+ }
+ if ptr.FromRoot != 0 && ptr.FromNode != 0 {
+ panic("kp.FromRoot and kp.FromNode should not both be set")
+ }
+ if (ptr.FromRoot == 0 && ptr.FromNode == 0) && ptr.FromItem != 0 {
+ panic("kp.FromItem should only be set if either kp.FromRoot or kp.FromItem is set")
+ }
+ g.EdgesFrom[ptr.FromNode] = append(g.EdgesFrom[ptr.FromNode], ptr)
+ g.EdgesTo[ptr.ToNode] = append(g.EdgesTo[ptr.ToNode], ptr)
+}
+
+func (g Graph) insertTreeRoot(sb btrfstree.Superblock, treeID btrfsprim.ObjID) {
+ treeInfo, err := btrfstree.LookupTreeRoot(nil, sb, treeID)
+ if err != nil {
+ // This shouldn't ever happen for treeIDs that are
+ // mentioned directly in the superblock; which are the
+ // only trees for which we should call
+ // .insertTreeRoot().
+ panic(fmt.Errorf("LookupTreeRoot(%v): %w", treeID, err))
+ }
+ if treeInfo.RootNode == 0 {
+ return
+ }
+ g.insertEdge(&Edge{
+ FromTree: treeID,
+ ToNode: treeInfo.RootNode,
+ ToLevel: treeInfo.Level,
+ ToGeneration: treeInfo.Generation,
+ })
+}
+
+func New(sb btrfstree.Superblock) *Graph {
+ g := &Graph{
+ Nodes: make(map[btrfsvol.LogicalAddr]Node),
+ BadNodes: make(map[btrfsvol.LogicalAddr]error),
+ EdgesFrom: make(map[btrfsvol.LogicalAddr][]*Edge),
+ EdgesTo: make(map[btrfsvol.LogicalAddr][]*Edge),
+ }
+
+ // These 4 trees are mentioned directly in the superblock, so
+ // they are always seen.
+ g.insertTreeRoot(sb, btrfsprim.ROOT_TREE_OBJECTID)
+ g.insertTreeRoot(sb, btrfsprim.CHUNK_TREE_OBJECTID)
+ g.insertTreeRoot(sb, btrfsprim.TREE_LOG_OBJECTID)
+ g.insertTreeRoot(sb, btrfsprim.BLOCK_GROUP_TREE_OBJECTID)
+
+ return g
+}
+
+func (g Graph) InsertNode(nodeRef *diskio.Ref[btrfsvol.LogicalAddr, btrfstree.Node]) {
+ nodeData := Node{
+ Level: nodeRef.Data.Head.Level,
+ Generation: nodeRef.Data.Head.Generation,
+ Owner: nodeRef.Data.Head.Owner,
+ NumItems: nodeRef.Data.Head.NumItems,
+ MinItem: discardOK(nodeRef.Data.MinItem()),
+ MaxItem: discardOK(nodeRef.Data.MaxItem()),
+ }
+
+ if nodeRef.Data.Head.Level == 0 {
+ cnt := 0
+ for _, item := range nodeRef.Data.BodyLeaf {
+ if _, ok := item.Body.(*btrfsitem.Root); ok {
+ cnt++
+ }
+ }
+ kps := make([]Edge, 0, cnt)
+ keys := make([]btrfsprim.Key, len(nodeRef.Data.BodyLeaf))
+ nodeData.Items = keys
+ g.Nodes[nodeRef.Addr] = nodeData
+ for i, item := range nodeRef.Data.BodyLeaf {
+ keys[i] = item.Key
+ if itemBody, ok := item.Body.(*btrfsitem.Root); ok {
+ kps = append(kps, Edge{
+ FromRoot: nodeRef.Addr,
+ FromItem: i,
+ FromTree: item.Key.ObjectID,
+ ToNode: itemBody.ByteNr,
+ ToLevel: itemBody.Level,
+ ToGeneration: itemBody.Generation,
+ })
+ g.insertEdge(&kps[len(kps)-1])
+ }
+ }
+ } else {
+ g.Nodes[nodeRef.Addr] = nodeData
+ kps := make([]Edge, len(nodeRef.Data.BodyInternal))
+ for i, kp := range nodeRef.Data.BodyInternal {
+ kps[i] = Edge{
+ FromNode: nodeRef.Addr,
+ FromItem: i,
+ FromTree: nodeRef.Data.Head.Owner,
+ ToNode: kp.BlockPtr,
+ ToLevel: nodeRef.Data.Head.Level - 1,
+ ToKey: kp.Key,
+ ToGeneration: kp.Generation,
+ }
+ g.insertEdge(&kps[i])
+ }
+ }
+}
+
+func (g Graph) FinalCheck(ctx context.Context, fs diskio.File[btrfsvol.LogicalAddr], sb btrfstree.Superblock) error {
+ var stats textui.Portion[int]
+ _ctx := ctx
+
+ ctx = dlog.WithField(_ctx, "btrfsinspect.rebuild-nodes.read.substep", "check-keypointers")
+ dlog.Info(_ctx, "Checking keypointers for dead-ends...")
+ progressWriter := textui.NewProgress[textui.Portion[int]](ctx, dlog.LogLevelInfo, textui.Tunable(1*time.Second))
+ stats.D = len(g.EdgesTo)
+ progressWriter.Set(stats)
+ 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},
+ })
+ if err == nil {
+ progressWriter.Done()
+ return fmt.Errorf("node@%v exists but was not in node scan results", laddr)
+ }
+ g.BadNodes[laddr] = err
+ }
+ stats.N++
+ progressWriter.Set(stats)
+ }
+ progressWriter.Done()
+ dlog.Info(ctx, "... done checking keypointers")
+
+ ctx = dlog.WithField(_ctx, "btrfsinspect.rebuild-nodes.read.substep", "check-for-loops")
+ dlog.Info(_ctx, "Checking for btree loops...")
+ stats.D = len(g.Nodes)
+ stats.N = 0
+ progressWriter = textui.NewProgress[textui.Portion[int]](ctx, dlog.LogLevelInfo, textui.Tunable(1*time.Second))
+ progressWriter.Set(stats)
+ visited := make(containers.Set[btrfsvol.LogicalAddr], len(g.Nodes))
+ numLoops := 0
+ var checkNode func(node btrfsvol.LogicalAddr, stack []btrfsvol.LogicalAddr)
+ checkNode = func(node btrfsvol.LogicalAddr, stack []btrfsvol.LogicalAddr) {
+ defer func() {
+ stats.N = len(visited)
+ progressWriter.Set(stats)
+ }()
+ if visited.Has(node) {
+ return
+ }
+ if slices.Contains(node, stack) {
+ numLoops++
+ dlog.Error(ctx, "loop:")
+ for _, line := range g.renderLoop(append(stack, node)) {
+ dlog.Errorf(ctx, " %s", line)
+ }
+ return
+ }
+ stack = append(stack, node)
+ for _, kp := range g.EdgesTo[node] {
+ checkNode(kp.FromNode, stack)
+ }
+ visited.Insert(node)
+ }
+ for _, node := range maps.SortedKeys(g.Nodes) {
+ checkNode(node, nil)
+ }
+ progressWriter.Done()
+ if numLoops > 0 {
+ return fmt.Errorf("%d btree loops", numLoops)
+ }
+ dlog.Info(_ctx, "... done checking for loops")
+
+ return nil
+}
+
+func discardOK[T any](val T, _ bool) T {
+ return val
+}
diff --git a/lib/btrfsutil/graph_loops.go b/lib/btrfsutil/graph_loops.go
new file mode 100644
index 0000000..0e51805
--- /dev/null
+++ b/lib/btrfsutil/graph_loops.go
@@ -0,0 +1,133 @@
+// Copyright (C) 2022 Luke Shumaker <lukeshu@lukeshu.com>
+//
+// SPDX-License-Identifier: GPL-2.0-or-later
+
+package graph
+
+import (
+ "fmt"
+ "strings"
+
+ "github.com/datawire/dlib/derror"
+
+ "git.lukeshu.com/btrfs-progs-ng/lib/btrfs/btrfsprim"
+ "git.lukeshu.com/btrfs-progs-ng/lib/btrfs/btrfsvol"
+)
+
+func (g Graph) renderNode(node btrfsvol.LogicalAddr) []string {
+ if node == 0 {
+ return []string{"root"}
+ } else if nodeData, ok := g.Nodes[node]; ok {
+ return []string{
+ fmt.Sprintf("{addr: %v,", node),
+ fmt.Sprintf(" level: %v,", nodeData.Level),
+ fmt.Sprintf(" gen: %v,", nodeData.Generation),
+ fmt.Sprintf(" num_items: %v,", nodeData.NumItems),
+ fmt.Sprintf(" min_item: {%d,%v,%d},",
+ nodeData.MinItem.ObjectID,
+ nodeData.MinItem.ItemType,
+ nodeData.MinItem.Offset),
+ fmt.Sprintf(" max_item: {%d,%v,%d}}",
+ nodeData.MaxItem.ObjectID,
+ nodeData.MaxItem.ItemType,
+ nodeData.MaxItem.Offset),
+ }
+ } else if nodeErr, ok := g.BadNodes[node]; ok {
+ return []string{
+ fmt.Sprintf("{addr:%v,", node),
+ fmt.Sprintf(" err:%q}", nodeErr.Error()),
+ }
+ } else {
+ panic("should not happen")
+ }
+}
+
+func (g Graph) renderEdge(kp Edge) []string {
+ a := fmt.Sprintf("[%d]={", kp.FromItem)
+ b := strings.Repeat(" ", len(a))
+ ret := []string{
+ a + fmt.Sprintf("ToNode: %v,", kp.ToNode),
+ b + fmt.Sprintf("ToLevel: %v,", kp.ToLevel),
+ b + fmt.Sprintf("ToGen: %v,", kp.ToGeneration),
+ b + fmt.Sprintf("ToKey: {%d,%v,%d}}",
+ kp.ToKey.ObjectID,
+ kp.ToKey.ItemType,
+ kp.ToKey.Offset),
+ }
+
+ var err error
+ if toNode, ok := g.Nodes[kp.ToNode]; !ok {
+ err = g.BadNodes[kp.ToNode]
+ } else {
+ err = checkNodeExpectations(kp, toNode)
+ }
+ if err != nil {
+ c := strings.Repeat(" ", len(a)-1)
+ ret = append(ret,
+ c+"^",
+ c+"`-err="+strings.ReplaceAll(err.Error(), "\n", "\n"+c+" "),
+ )
+ }
+ return ret
+}
+
+func (g Graph) renderLoop(stack []btrfsvol.LogicalAddr) []string {
+ var lines []string
+ add := func(suffixes []string) {
+ curLen := 0
+ for _, line := range lines {
+ if len(line) > curLen {
+ curLen = len(line)
+ }
+ }
+ for i, suffix := range suffixes {
+ if len(lines) <= i {
+ lines = append(lines, "")
+ }
+ if len(lines[i]) < curLen {
+ if i == 0 {
+ lines[i] += strings.Repeat("-", curLen-len(lines[i])-1) + ">"
+ } else {
+ lines[i] += strings.Repeat(" ", curLen-len(lines[i]))
+ }
+ }
+ lines[i] += suffix
+ }
+ }
+
+ for i, node := range stack {
+ if i > 0 {
+ for _, kp := range g.EdgesTo[node] {
+ if kp.FromNode == stack[i-1] {
+ add(g.renderEdge(*kp))
+ break
+ }
+ }
+ }
+ add(g.renderNode(node))
+ }
+
+ return lines
+}
+
+func checkNodeExpectations(kp Edge, toNode Node) error {
+ var errs derror.MultiError
+ if toNode.Level != kp.ToLevel {
+ errs = append(errs, fmt.Errorf("kp.level=%v != node.level=%v",
+ kp.ToLevel, toNode.Level))
+ }
+ if toNode.Generation != kp.ToGeneration {
+ errs = append(errs, fmt.Errorf("kp.generation=%v != node.generation=%v",
+ kp.ToGeneration, toNode.Generation))
+ }
+ if toNode.NumItems == 0 {
+ errs = append(errs, fmt.Errorf("node.num_items=0"))
+ } else if kp.ToKey != (btrfsprim.Key{}) && toNode.MinItem != kp.ToKey {
+ errs = append(errs, fmt.Errorf("kp.key=%v != node.items[0].key=%v",
+ kp.ToKey, toNode.MinItem))
+ }
+ if len(errs) > 0 {
+ return errs
+ }
+ return nil
+}
diff --git a/lib/btrfsutil/nestedlock.go b/lib/btrfsutil/nestedlock.go
new file mode 100644
index 0000000..c1ffa18
--- /dev/null
+++ b/lib/btrfsutil/nestedlock.go
@@ -0,0 +1,45 @@
+// Copyright (C) 2023 Luke Shumaker <lukeshu@lukeshu.com>
+//
+// SPDX-License-Identifier: GPL-2.0-or-later
+
+package btrees
+
+import (
+ "context"
+ "sync"
+)
+
+// A nestedMutex is like a sync.Mutex, but while it is locked by call
+// 'A', may be simultaneously locked by subsequent calls if the
+// subsequent calls use a Context descended from the one returned by
+// the 'A' call to .Lock().
+type nestedMutex struct {
+ inner sync.Mutex
+ depth int
+}
+
+type nestedMutexCtxKey struct{}
+
+// Lock locks the mutex. It is invalid to use a Context returned from
+// Lock in a different goroutine than the one it was created in. It
+// is invalid to use a Context returned from Lock after the mutex has
+// subsequently become unlocked.
+func (m *nestedMutex) Lock(ctx context.Context) context.Context {
+ if other, ok := ctx.Value(nestedMutexCtxKey{}).(*nestedMutex); ok && other == m {
+ m.depth++
+ return ctx
+ }
+ m.inner.Lock()
+ return context.WithValue(ctx, nestedMutexCtxKey{}, m)
+}
+
+// Unlock unlocks the mutex. It is invalid to call Unlock if the
+// mutex is not already locked. It is invalid to call Unlock from
+// multiple goroutines simultaneously.
+func (m *nestedMutex) Unlock() {
+ if m.depth > 0 {
+ m.depth--
+ } else {
+ m.inner.Unlock()
+ }
+}
diff --git a/lib/btrfsutil/old_rebuilt_forrest.go b/lib/btrfsutil/old_rebuilt_forrest.go
new file mode 100644
index 0000000..b7663fa
--- /dev/null
+++ b/lib/btrfsutil/old_rebuilt_forrest.go
@@ -0,0 +1,363 @@
+// Copyright (C) 2022-2023 Luke Shumaker <lukeshu@lukeshu.com>
+//
+// SPDX-License-Identifier: GPL-2.0-or-later
+
+package btrfsutil
+
+import (
+ "context"
+ "fmt"
+ iofs "io/fs"
+ "sync"
+
+ "github.com/datawire/dlib/derror"
+ "github.com/datawire/dlib/dlog"
+
+ "git.lukeshu.com/btrfs-progs-ng/lib/btrfs"
+ "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/diskio"
+)
+
+type treeIndex struct {
+ TreeRootErr error
+ Items *containers.RBTree[treeIndexValue]
+ Errors *containers.IntervalTree[btrfsprim.Key, treeIndexError]
+}
+
+type treeIndexError struct {
+ Path SkinnyPath
+ Err error
+}
+
+type treeIndexValue struct {
+ Path SkinnyPath
+ Key btrfsprim.Key
+ ItemSize uint32
+}
+
+// Compare implements containers.Ordered.
+func (a treeIndexValue) Compare(b treeIndexValue) int {
+ return a.Key.Compare(b.Key)
+}
+
+func newTreeIndex(arena *SkinnyPathArena) treeIndex {
+ return treeIndex{
+ Items: new(containers.RBTree[treeIndexValue]),
+ Errors: &containers.IntervalTree[btrfsprim.Key, treeIndexError]{
+ MinFn: func(err treeIndexError) btrfsprim.Key {
+ return arena.Inflate(err.Path).Node(-1).ToKey
+ },
+ MaxFn: func(err treeIndexError) btrfsprim.Key {
+ return arena.Inflate(err.Path).Node(-1).ToMaxKey
+ },
+ },
+ }
+}
+
+type brokenTrees 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
+ rootTreeIndex *treeIndex
+ // for all other trees
+ treeMu sync.Mutex
+ treeIndexes map[btrfsprim.ObjID]treeIndex
+}
+
+var _ btrfstree.TreeOperator = (*brokenTrees)(nil)
+
+// NewBrokenTrees wraps a *btrfs.FS to support looking up information
+// from broken trees.
+//
+// Of the btrfstree.TreeOperator methods:
+//
+// - TreeWalk works on broken trees
+// - TreeLookup relies on the tree being properly ordered (which a
+// broken tree might not be).
+// - TreeSearch relies on the tree being properly ordered (which a
+// broken tree might not be).
+// - TreeSearchAll relies on the tree being properly ordered (which a
+// broken tree might not be), and a bad node may cause it to not
+// return a truncated list of results.
+//
+// NewBrokenTrees attempts to remedy these deficiencies by using
+// .TreeWalk to build an out-of-FS index of all of the items in the
+// tree, and re-implements TreeLookup, TreeSearch, and TreeSearchAll
+// using that index.
+func NewBrokenTrees(ctx context.Context, inner *btrfs.FS) interface {
+ btrfstree.TreeOperator
+ Superblock() (*btrfstree.Superblock, error)
+ ReadAt(p []byte, off btrfsvol.LogicalAddr) (int, error)
+ Augment(treeID btrfsprim.ObjID, nodeAddr btrfsvol.LogicalAddr) ([]btrfsprim.Key, error)
+} {
+ return &brokenTrees{
+ ctx: ctx,
+ inner: inner,
+ }
+}
+
+func (bt *brokenTrees) treeIndex(treeID btrfsprim.ObjID) treeIndex {
+ 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.rootTreeIndex != nil {
+ return *bt.rootTreeIndex
+ }
+ sb, err = bt.inner.Superblock()
+ if err == nil {
+ treeRoot, err = btrfstree.LookupTreeRoot(bt.inner, *sb, treeID)
+ }
+ } else {
+ bt.treeMu.Lock()
+ defer bt.treeMu.Unlock()
+ if bt.treeIndexes == nil {
+ bt.treeIndexes = make(map[btrfsprim.ObjID]treeIndex)
+ }
+ if cacheEntry, exists := bt.treeIndexes[treeID]; exists {
+ return cacheEntry
+ }
+ sb, err = bt.inner.Superblock()
+ if err == nil {
+ 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 := newTreeIndex(bt.arena)
+ if err != nil {
+ cacheEntry.TreeRootErr = err
+ } else {
+ dlog.Infof(bt.ctx, "indexing tree %v...", treeID)
+ bt.rawTreeWalk(*treeRoot, cacheEntry, nil)
+ dlog.Infof(bt.ctx, "... done indexing tree %v", treeID)
+ }
+ if treeID == btrfsprim.ROOT_TREE_OBJECTID {
+ bt.rootTreeIndex = &cacheEntry
+ } else {
+ bt.treeIndexes[treeID] = cacheEntry
+ }
+ return cacheEntry
+}
+
+func (bt *brokenTrees) rawTreeWalk(root btrfstree.TreeRoot, cacheEntry treeIndex, walked *[]btrfsprim.Key) {
+ btrfstree.TreeOperatorImpl{NodeSource: bt.inner}.RawTreeWalk(
+ bt.ctx,
+ root,
+ 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
+ // indicates a bug in my item parser than a problem with the filesystem.
+ panic(fmt.Errorf("TODO: error parsing item: %w", err))
+ }
+ cacheEntry.Errors.Insert(treeIndexError{
+ Path: bt.arena.Deflate(err.Path),
+ Err: err.Err,
+ })
+ },
+ btrfstree.TreeWalkHandler{
+ Item: func(path btrfstree.TreePath, item btrfstree.Item) error {
+ if cacheEntry.Items.Search(func(v treeIndexValue) 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
+ // and force me to figure out how to handle it.
+ panic(fmt.Errorf("dup key=%v in tree=%v", item.Key, root.TreeID))
+ }
+ cacheEntry.Items.Insert(treeIndexValue{
+ Path: bt.arena.Deflate(path),
+ Key: item.Key,
+ ItemSize: item.BodySize,
+ })
+ if walked != nil {
+ *walked = append(*walked, item.Key)
+ }
+ return nil
+ },
+ },
+ )
+}
+
+func (bt *brokenTrees) TreeLookup(treeID btrfsprim.ObjID, key btrfsprim.Key) (btrfstree.Item, error) {
+ item, err := bt.TreeSearch(treeID, btrfstree.KeySearch(key.Compare))
+ if err != nil {
+ err = fmt.Errorf("item with key=%v: %w", key, err)
+ }
+ return item, err
+}
+
+func (bt *brokenTrees) addErrs(index treeIndex, fn func(btrfsprim.Key, uint32) int, err error) error {
+ var errs derror.MultiError
+ index.Errors.Subrange(
+ func(k btrfsprim.Key) int { return fn(k, 0) },
+ func(v treeIndexError) bool {
+ errs = append(errs, &btrfstree.TreeError{
+ Path: bt.arena.Inflate(v.Path),
+ Err: v.Err,
+ })
+ return true
+ })
+ if len(errs) == 0 {
+ return err
+ }
+ if err != nil {
+ errs = append(errs, err)
+ }
+ return errs
+}
+
+func (bt *brokenTrees) TreeSearch(treeID btrfsprim.ObjID, fn func(btrfsprim.Key, uint32) int) (btrfstree.Item, error) {
+ index := bt.treeIndex(treeID)
+ if index.TreeRootErr != nil {
+ return btrfstree.Item{}, index.TreeRootErr
+ }
+
+ indexItem := index.Items.Search(func(indexItem treeIndexValue) int {
+ return fn(indexItem.Key, indexItem.ItemSize)
+ })
+ if indexItem == nil {
+ return btrfstree.Item{}, bt.addErrs(index, fn, iofs.ErrNotExist)
+ }
+
+ itemPath := bt.arena.Inflate(indexItem.Value.Path)
+ node, err := bt.inner.ReadNode(itemPath.Parent())
+ defer btrfstree.FreeNodeRef(node)
+ if err != nil {
+ return btrfstree.Item{}, bt.addErrs(index, fn, err)
+ }
+
+ item := node.Data.BodyLeaf[itemPath.Node(-1).FromItemIdx]
+ 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().
+ return item, nil
+}
+
+func (bt *brokenTrees) TreeSearchAll(treeID btrfsprim.ObjID, fn func(btrfsprim.Key, uint32) int) ([]btrfstree.Item, error) {
+ index := bt.treeIndex(treeID)
+ if index.TreeRootErr != nil {
+ return nil, index.TreeRootErr
+ }
+
+ var indexItems []treeIndexValue
+ index.Items.Subrange(
+ func(indexItem treeIndexValue) int { return fn(indexItem.Key, indexItem.ItemSize) },
+ func(node *containers.RBNode[treeIndexValue]) bool {
+ indexItems = append(indexItems, node.Value)
+ return true
+ })
+ if len(indexItems) == 0 {
+ return nil, bt.addErrs(index, fn, iofs.ErrNotExist)
+ }
+
+ ret := make([]btrfstree.Item, len(indexItems))
+ var node *diskio.Ref[btrfsvol.LogicalAddr, btrfstree.Node]
+ for i := range indexItems {
+ itemPath := bt.arena.Inflate(indexItems[i].Path)
+ if node == nil || node.Addr != itemPath.Node(-2).ToNodeAddr {
+ var err error
+ btrfstree.FreeNodeRef(node)
+ node, err = bt.inner.ReadNode(itemPath.Parent())
+ if err != nil {
+ btrfstree.FreeNodeRef(node)
+ return nil, bt.addErrs(index, fn, err)
+ }
+ }
+ ret[i] = node.Data.BodyLeaf[itemPath.Node(-1).FromItemIdx]
+ ret[i].Body = ret[i].Body.CloneItem()
+ }
+ btrfstree.FreeNodeRef(node)
+
+ return ret, bt.addErrs(index, fn, nil)
+}
+
+func (bt *brokenTrees) TreeWalk(ctx context.Context, treeID btrfsprim.ObjID, errHandle func(*btrfstree.TreeError), cbs btrfstree.TreeWalkHandler) {
+ index := bt.treeIndex(treeID)
+ if index.TreeRootErr != nil {
+ errHandle(&btrfstree.TreeError{
+ Path: btrfstree.TreePath{{
+ FromTree: treeID,
+ ToMaxKey: btrfsprim.MaxKey,
+ }},
+ Err: index.TreeRootErr,
+ })
+ return
+ }
+ var node *diskio.Ref[btrfsvol.LogicalAddr, btrfstree.Node]
+ index.Items.Range(func(indexItem *containers.RBNode[treeIndexValue]) bool {
+ if ctx.Err() != nil {
+ return false
+ }
+ if bt.ctx.Err() != nil {
+ return false
+ }
+ if cbs.Item != nil {
+ itemPath := bt.arena.Inflate(indexItem.Value.Path)
+ if node == nil || node.Addr != itemPath.Node(-2).ToNodeAddr {
+ var err error
+ btrfstree.FreeNodeRef(node)
+ node, err = bt.inner.ReadNode(itemPath.Parent())
+ if err != nil {
+ btrfstree.FreeNodeRef(node)
+ errHandle(&btrfstree.TreeError{Path: itemPath, Err: err})
+ return true
+ }
+ }
+ item := node.Data.BodyLeaf[itemPath.Node(-1).FromItemIdx]
+ if err := cbs.Item(itemPath, item); err != nil {
+ errHandle(&btrfstree.TreeError{Path: itemPath, Err: err})
+ }
+ }
+ return true
+ })
+ btrfstree.FreeNodeRef(node)
+}
+
+func (bt *brokenTrees) Superblock() (*btrfstree.Superblock, error) {
+ return bt.inner.Superblock()
+}
+
+func (bt *brokenTrees) ReadAt(p []byte, off btrfsvol.LogicalAddr) (int, error) {
+ return bt.inner.ReadAt(p, off)
+}
+
+func (bt *brokenTrees) Augment(treeID btrfsprim.ObjID, nodeAddr btrfsvol.LogicalAddr) ([]btrfsprim.Key, error) {
+ sb, err := bt.Superblock()
+ if err != nil {
+ return nil, err
+ }
+ index := bt.treeIndex(treeID)
+ if index.TreeRootErr != nil {
+ return nil, index.TreeRootErr
+ }
+ nodeRef, err := btrfstree.ReadNode[btrfsvol.LogicalAddr](bt.inner, *sb, nodeAddr, btrfstree.NodeExpectations{})
+ defer btrfstree.FreeNodeRef(nodeRef)
+ if err != nil {
+ return nil, err
+ }
+ var ret []btrfsprim.Key
+ bt.rawTreeWalk(btrfstree.TreeRoot{
+ TreeID: treeID,
+ RootNode: nodeAddr,
+ Level: nodeRef.Data.Head.Level,
+ Generation: nodeRef.Data.Head.Generation,
+ }, index, &ret)
+ return ret, nil
+}
diff --git a/lib/btrfsutil/open.go b/lib/btrfsutil/open.go
new file mode 100644
index 0000000..c5ee314
--- /dev/null
+++ b/lib/btrfsutil/open.go
@@ -0,0 +1,46 @@
+// Copyright (C) 2022-2023 Luke Shumaker <lukeshu@lukeshu.com>
+//
+// SPDX-License-Identifier: GPL-2.0-or-later
+
+package btrfsutil
+
+import (
+ "context"
+ "fmt"
+ "os"
+
+ "github.com/datawire/dlib/dlog"
+
+ "git.lukeshu.com/btrfs-progs-ng/lib/btrfs"
+ "git.lukeshu.com/btrfs-progs-ng/lib/btrfs/btrfsvol"
+ "git.lukeshu.com/btrfs-progs-ng/lib/diskio"
+ "git.lukeshu.com/btrfs-progs-ng/lib/textui"
+)
+
+func Open(ctx context.Context, flag int, filenames ...string) (*btrfs.FS, error) {
+ fs := new(btrfs.FS)
+ for i, filename := range filenames {
+ dlog.Debugf(ctx, "Adding device file %d/%d %q...", i, len(filenames), filename)
+ osFile, err := os.OpenFile(filename, flag, 0)
+ if err != nil {
+ _ = fs.Close()
+ return nil, fmt.Errorf("device file %q: %w", filename, err)
+ }
+ typedFile := &diskio.OSFile[btrfsvol.PhysicalAddr]{
+ File: osFile,
+ }
+ bufFile := diskio.NewBufferedFile[btrfsvol.PhysicalAddr](
+ typedFile,
+ //nolint:gomnd // False positive: gomnd.ignored-functions=[textui.Tunable] doesn't support type params.
+ textui.Tunable[btrfsvol.PhysicalAddr](16*1024), // block size: 16KiB
+ textui.Tunable(1024), // number of blocks to buffer; total of 16MiB
+ )
+ devFile := &btrfs.Device{
+ File: bufFile,
+ }
+ if err := fs.AddDevice(ctx, devFile); err != nil {
+ return nil, fmt.Errorf("device file %q: %w", filename, err)
+ }
+ }
+ return fs, nil
+}
diff --git a/lib/btrfsutil/print_addrspace.go b/lib/btrfsutil/print_addrspace.go
new file mode 100644
index 0000000..e85e055
--- /dev/null
+++ b/lib/btrfsutil/print_addrspace.go
@@ -0,0 +1,73 @@
+// Copyright (C) 2022-2023 Luke Shumaker <lukeshu@lukeshu.com>
+//
+// SPDX-License-Identifier: GPL-2.0-or-later
+
+package btrfsinspect
+
+import (
+ "io"
+ "sort"
+
+ "git.lukeshu.com/btrfs-progs-ng/lib/btrfs"
+ "git.lukeshu.com/btrfs-progs-ng/lib/btrfs/btrfsvol"
+ "git.lukeshu.com/btrfs-progs-ng/lib/textui"
+)
+
+func PrintLogicalSpace(out io.Writer, fs *btrfs.FS) {
+ mappings := fs.LV.Mappings()
+ var prevBeg, prevEnd btrfsvol.LogicalAddr
+ var sumHole, sumChunk btrfsvol.AddrDelta
+ for _, mapping := range mappings {
+ if mapping.LAddr > prevEnd {
+ size := mapping.LAddr.Sub(prevEnd)
+ textui.Fprintf(out, "logical_hole laddr=%v size=%v\n", prevEnd, size)
+ sumHole += size
+ }
+ if mapping.LAddr != prevBeg {
+ if !mapping.Flags.OK {
+ textui.Fprintf(out, "chunk laddr=%v size=%v flags=(missing)\n",
+ mapping.LAddr, mapping.Size)
+ } else {
+ textui.Fprintf(out, "chunk laddr=%v size=%v flags=%v\n",
+ mapping.LAddr, mapping.Size, mapping.Flags.Val)
+ }
+ }
+ textui.Fprintf(out, "\tstripe dev_id=%v paddr=%v\n",
+ mapping.PAddr.Dev, mapping.PAddr.Addr)
+ sumChunk += mapping.Size
+ prevBeg = mapping.LAddr
+ prevEnd = mapping.LAddr.Add(mapping.Size)
+ }
+ textui.Fprintf(out, "total logical holes = %v (%d)\n", sumHole, int64(sumHole))
+ textui.Fprintf(out, "total logical chunks = %v (%d)\n", sumChunk, int64(sumChunk))
+ textui.Fprintf(out, "total logical addr space = %v (%d)\n", prevEnd, int64(prevEnd))
+}
+
+func PrintPhysicalSpace(out io.Writer, fs *btrfs.FS) {
+ mappings := fs.LV.Mappings()
+ sort.Slice(mappings, func(i, j int) bool {
+ return mappings[i].PAddr.Compare(mappings[j].PAddr) < 0
+ })
+
+ var prevDev btrfsvol.DeviceID = 0
+ var prevEnd btrfsvol.PhysicalAddr
+ var sumHole, sumExt btrfsvol.AddrDelta
+ for _, mapping := range mappings {
+ if mapping.PAddr.Dev != prevDev {
+ prevDev = mapping.PAddr.Dev
+ prevEnd = 0
+ }
+ if mapping.PAddr.Addr > prevEnd {
+ size := mapping.PAddr.Addr.Sub(prevEnd)
+ textui.Fprintf(out, "physical_hole paddr=%v size=%v\n", prevEnd, size)
+ sumHole += size
+ }
+ textui.Fprintf(out, "devext dev=%v paddr=%v size=%v laddr=%v\n",
+ mapping.PAddr.Dev, mapping.PAddr.Addr, mapping.Size, mapping.LAddr)
+ sumExt += mapping.Size
+ prevEnd = mapping.PAddr.Addr.Add(mapping.Size)
+ }
+ textui.Fprintf(out, "total physical holes = %v (%d)\n", sumHole, int64(sumHole))
+ textui.Fprintf(out, "total physical extents = %v (%d)\n", sumExt, int64(sumExt))
+ textui.Fprintf(out, "total physical addr space = %v (%d)\n", prevEnd, int64(prevEnd))
+}
diff --git a/lib/btrfsutil/rebuilt_forrest.go b/lib/btrfsutil/rebuilt_forrest.go
new file mode 100644
index 0000000..dbbc6eb
--- /dev/null
+++ b/lib/btrfsutil/rebuilt_forrest.go
@@ -0,0 +1,208 @@
+// Copyright (C) 2022-2023 Luke Shumaker <lukeshu@lukeshu.com>
+//
+// SPDX-License-Identifier: GPL-2.0-or-later
+
+package btrees
+
+import (
+ "context"
+
+ "github.com/datawire/dlib/dlog"
+
+ "git.lukeshu.com/btrfs-progs-ng/lib/btrfs/btrfsitem"
+ "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"
+ pkggraph "git.lukeshu.com/btrfs-progs-ng/lib/btrfsprogs/btrfsinspect/rebuildnodes/graph"
+ "git.lukeshu.com/btrfs-progs-ng/lib/btrfsprogs/btrfsinspect/rebuildnodes/keyio"
+ "git.lukeshu.com/btrfs-progs-ng/lib/containers"
+ "git.lukeshu.com/btrfs-progs-ng/lib/slices"
+ "git.lukeshu.com/btrfs-progs-ng/lib/textui"
+)
+
+type Callbacks interface {
+ AddedItem(ctx context.Context, tree btrfsprim.ObjID, key btrfsprim.Key)
+ AddedRoot(ctx context.Context, tree btrfsprim.ObjID, root btrfsvol.LogicalAddr)
+ LookupRoot(ctx context.Context, tree btrfsprim.ObjID) (offset btrfsprim.Generation, item btrfsitem.Root, ok bool)
+ LookupUUID(ctx context.Context, uuid btrfsprim.UUID) (id btrfsprim.ObjID, ok bool)
+}
+
+// RebuiltForrest is an abstraction for rebuilding and accessing
+// potentially broken btrees.
+//
+// It is conceptually a btrfstree.TreeOperator, and adds similar
+// broken-tree handling to btrfsutil.BrokenForrest. However, the API
+// is different thant btrfstree.TreeOperator, and is much more
+// efficient than btrfsutil.BrokenForrest.
+//
+// The efficiency improvements are possible because of the API
+// differences, which are necessary for how it is used in
+// rebuildnodes:
+//
+// - it consumes an already-read graph.Graph instead of reading the
+// graph itself
+//
+// - it does not use `btrfstree.TreePath`
+//
+// - it does not keep track of errors encountered in a tree
+//
+// Additionally, it provides some functionality that
+// btrfsutil.BrokenForrest does not:
+//
+// - it provides a .LeafToRoots() method to advise on what
+// additional roots should be added
+//
+// - it provides a .COWDistance() method to compare how related two
+// trees are
+//
+// A zero RebuiltForrest is invalid; it must be initialized with
+// NewRebuiltForrest().
+type RebuiltForrest struct {
+ // static
+ sb btrfstree.Superblock
+ graph pkggraph.Graph
+ keyIO *keyio.Handle
+ cb Callbacks
+
+ // mutable
+ treesMu nestedMutex
+ trees map[btrfsprim.ObjID]*RebuiltTree // must hold .treesMu to access
+ 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
+// the callbacks must be non-nil.
+func NewRebuiltForrest(sb btrfstree.Superblock, graph pkggraph.Graph, keyIO *keyio.Handle, cb Callbacks) *RebuiltForrest {
+ return &RebuiltForrest{
+ sb: sb,
+ graph: graph,
+ keyIO: keyIO,
+ cb: cb,
+
+ trees: make(map[btrfsprim.ObjID]*RebuiltTree),
+ 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),
+ },
+ }
+}
+
+// Tree returns a given tree, initializing it if nescessary. If it is
+// unable to initialize the tree, then nil is returned, and nothing is
+// done to the forrest.
+//
+// The tree is initialized with the normal root node of the tree.
+func (ts *RebuiltForrest) Tree(ctx context.Context, treeID btrfsprim.ObjID) *RebuiltTree {
+ ctx = ts.treesMu.Lock(ctx)
+ defer ts.treesMu.Unlock()
+ if !ts.addTree(ctx, treeID, nil) {
+ return nil
+ }
+ return ts.trees[treeID]
+}
+
+func (ts *RebuiltForrest) addTree(ctx context.Context, treeID btrfsprim.ObjID, stack []btrfsprim.ObjID) (ok bool) {
+ if tree, ok := ts.trees[treeID]; ok {
+ return tree != nil
+ }
+ defer func() {
+ if !ok {
+ // Store a negative cache of this. tree.AddRoot() for the ROOT or UUID
+ // trees will call .flushNegativeCache().
+ ts.trees[treeID] = nil
+ }
+ }()
+ stack = append(stack, treeID)
+ ctx = dlog.WithField(ctx, "btrfsinspect.rebuild-nodes.rebuild.add-tree", stack)
+ dlog.Info(ctx, "adding tree...")
+ if slices.Contains(treeID, stack[:len(stack)-1]) {
+ dlog.Errorf(ctx, "failed to add tree: loop detected: %v", stack)
+ return false
+ }
+
+ tree := &RebuiltTree{
+ ID: treeID,
+ Roots: make(containers.Set[btrfsvol.LogicalAddr]),
+ forrest: ts,
+ }
+ var root btrfsvol.LogicalAddr
+ switch treeID {
+ case btrfsprim.ROOT_TREE_OBJECTID:
+ root = ts.sb.RootTree
+ case btrfsprim.CHUNK_TREE_OBJECTID:
+ root = ts.sb.ChunkTree
+ case btrfsprim.TREE_LOG_OBJECTID:
+ root = ts.sb.LogTree
+ case btrfsprim.BLOCK_GROUP_TREE_OBJECTID:
+ root = ts.sb.BlockGroupRoot
+ default:
+ if !ts.addTree(ctx, btrfsprim.ROOT_TREE_OBJECTID, stack) {
+ dlog.Error(ctx, "failed to add tree: add ROOT_TREE")
+ return false
+ }
+ rootOff, rootItem, ok := ts.cb.LookupRoot(ctx, treeID)
+ if !ok {
+ dlog.Error(ctx, "failed to add tree: lookup ROOT_ITEM")
+ return false
+ }
+ root = rootItem.ByteNr
+ tree.UUID = rootItem.UUID
+ if rootItem.ParentUUID != (btrfsprim.UUID{}) {
+ tree.ParentGen = rootOff
+ if !ts.addTree(ctx, btrfsprim.UUID_TREE_OBJECTID, stack) {
+ return false
+ }
+ parentID, ok := ts.cb.LookupUUID(ctx, rootItem.ParentUUID)
+ if !ok {
+ dlog.Error(ctx, "failed to add tree: lookup UUID")
+ return false
+ }
+ if !ts.addTree(ctx, parentID, stack) {
+ dlog.Error(ctx, "failed to add tree: add parent tree")
+ return false
+ }
+ tree.Parent = ts.trees[parentID]
+ }
+ }
+
+ ts.trees[treeID] = tree
+ if root != 0 {
+ tree.AddRoot(ctx, root)
+ }
+
+ return true
+}
+
+func (ts *RebuiltForrest) flushNegativeCache(ctx context.Context) {
+ _ = ts.treesMu.Lock(ctx)
+ defer ts.treesMu.Unlock()
+ for treeID, tree := range ts.trees {
+ if tree == nil {
+ delete(ts.trees, treeID)
+ }
+ }
+}
+
+// ListRoots returns a listing of all initialized trees and their root
+// nodes.
+//
+// Do not mutate the set of roots for a tree; it is a pointer to the
+// RebuiltForrest's internal set!
+func (ts *RebuiltForrest) ListRoots(ctx context.Context) map[btrfsprim.ObjID]containers.Set[btrfsvol.LogicalAddr] {
+ _ = ts.treesMu.Lock(ctx)
+ defer ts.treesMu.Unlock()
+ ret := make(map[btrfsprim.ObjID]containers.Set[btrfsvol.LogicalAddr])
+ for treeID, tree := range ts.trees {
+ if tree != nil {
+ ret[treeID] = tree.Roots
+ }
+ }
+ return ret
+}
diff --git a/lib/btrfsutil/rebuilt_readitem.go b/lib/btrfsutil/rebuilt_readitem.go
new file mode 100644
index 0000000..56da32d
--- /dev/null
+++ b/lib/btrfsutil/rebuilt_readitem.go
@@ -0,0 +1,172 @@
+// Copyright (C) 2022-2023 Luke Shumaker <lukeshu@lukeshu.com>
+//
+// SPDX-License-Identifier: GPL-2.0-or-later
+
+package keyio
+
+import (
+ "context"
+ "fmt"
+ "sync"
+
+ "github.com/datawire/dlib/dlog"
+
+ "git.lukeshu.com/btrfs-progs-ng/lib/btrfs/btrfsitem"
+ "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/rebuildnodes/graph"
+ "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 ItemPtr struct {
+ Node btrfsvol.LogicalAddr
+ Idx int
+}
+
+func (ptr ItemPtr) String() string {
+ return fmt.Sprintf("node@%v[%v]", ptr.Node, ptr.Idx)
+}
+
+type SizeAndErr struct {
+ Size uint64
+ Err error
+}
+
+type FlagsAndErr struct {
+ NoDataSum bool
+ Err error
+}
+
+type Handle struct {
+ rawFile diskio.File[btrfsvol.LogicalAddr]
+ sb btrfstree.Superblock
+ graph graph.Graph
+
+ Flags map[ItemPtr]FlagsAndErr // INODE_ITEM
+ Names map[ItemPtr][]byte // DIR_INDEX
+ Sizes map[ItemPtr]SizeAndErr // EXTENT_CSUM and EXTENT_DATA
+
+ mu sync.Mutex
+ cache containers.ARCache[btrfsvol.LogicalAddr, *diskio.Ref[btrfsvol.LogicalAddr, btrfstree.Node]]
+}
+
+func NewHandle(file diskio.File[btrfsvol.LogicalAddr], sb btrfstree.Superblock) *Handle {
+ return &Handle{
+ rawFile: file,
+ sb: sb,
+
+ Flags: make(map[ItemPtr]FlagsAndErr),
+ Names: make(map[ItemPtr][]byte),
+ Sizes: make(map[ItemPtr]SizeAndErr),
+
+ 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)
+ },
+ },
+ }
+}
+
+func (o *Handle) InsertNode(nodeRef *diskio.Ref[btrfsvol.LogicalAddr, btrfstree.Node]) {
+ for i, item := range nodeRef.Data.BodyLeaf {
+ ptr := ItemPtr{
+ Node: nodeRef.Addr,
+ Idx: i,
+ }
+ switch itemBody := item.Body.(type) {
+ case *btrfsitem.Inode:
+ o.Flags[ptr] = FlagsAndErr{
+ NoDataSum: itemBody.Flags.Has(btrfsitem.INODE_NODATASUM),
+ Err: nil,
+ }
+ case *btrfsitem.DirEntry:
+ if item.Key.ItemType == btrfsprim.DIR_INDEX_KEY {
+ o.Names[ptr] = append([]byte(nil), itemBody.Name...)
+ }
+ case *btrfsitem.ExtentCSum:
+ o.Sizes[ptr] = SizeAndErr{
+ Size: uint64(itemBody.Size()),
+ Err: nil,
+ }
+ case *btrfsitem.FileExtent:
+ size, err := itemBody.Size()
+ o.Sizes[ptr] = SizeAndErr{
+ Size: uint64(size),
+ Err: err,
+ }
+ case *btrfsitem.Error:
+ switch item.Key.ItemType {
+ case btrfsprim.INODE_ITEM_KEY:
+ o.Flags[ptr] = FlagsAndErr{
+ Err: fmt.Errorf("error decoding item: ptr=%v (tree=%v key=%v): %w",
+ ptr, nodeRef.Data.Head.Owner, item.Key, itemBody.Err),
+ }
+ case btrfsprim.EXTENT_CSUM_KEY, btrfsprim.EXTENT_DATA_KEY:
+ o.Sizes[ptr] = SizeAndErr{
+ Err: fmt.Errorf("error decoding item: ptr=%v (tree=%v key=%v): %w",
+ ptr, nodeRef.Data.Head.Owner, item.Key, itemBody.Err),
+ }
+ }
+ }
+ }
+}
+
+func (o *Handle) SetGraph(graph graph.Graph) {
+ o.graph = graph
+}
+
+func (o *Handle) readNode(ctx context.Context, laddr btrfsvol.LogicalAddr) *diskio.Ref[btrfsvol.LogicalAddr, btrfstree.Node] {
+ if cached, ok := o.cache.Load(laddr); ok {
+ dlog.Tracef(ctx, "cache-hit node@%v", laddr)
+ return cached
+ }
+
+ graphInfo, ok := o.graph.Nodes[laddr]
+ if !ok {
+ panic(fmt.Errorf("should not happen: node@%v is not mentioned in the in-memory graph", laddr))
+ }
+
+ dlog.Debugf(ctx, "cache-miss node@%v, reading...", laddr)
+ ref, err := btrfstree.ReadNode(o.rawFile, o.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},
+ Owner: func(treeID btrfsprim.ObjID) error {
+ if treeID != graphInfo.Owner {
+ return fmt.Errorf("expected owner=%v but claims to have owner=%v",
+ graphInfo.Owner, treeID)
+ }
+ return nil
+ },
+ MinItem: containers.Optional[btrfsprim.Key]{OK: true, Val: graphInfo.MinItem},
+ MaxItem: containers.Optional[btrfsprim.Key]{OK: true, Val: graphInfo.MaxItem},
+ })
+ if err != nil {
+ panic(fmt.Errorf("should not happen: i/o error: %w", err))
+ }
+
+ o.cache.Store(laddr, ref)
+
+ return ref
+}
+
+func (o *Handle) ReadItem(ctx context.Context, ptr ItemPtr) btrfsitem.Item {
+ o.mu.Lock()
+ defer o.mu.Unlock()
+ if o.graph.Nodes[ptr.Node].Level != 0 {
+ panic(fmt.Errorf("should not happen: keyio.Handle.ReadItem called for non-leaf node@%v", ptr.Node))
+ }
+ if ptr.Idx < 0 {
+ panic(fmt.Errorf("should not happen: keyio.Handle.ReadItem called for negative item index: %v", ptr.Idx))
+ }
+ items := o.readNode(ctx, ptr.Node).Data.BodyLeaf
+ if ptr.Idx >= len(items) {
+ panic(fmt.Errorf("should not happen: keyio.Handle.ReadItem called for out-of-bounds item index: index=%v len=%v",
+ ptr.Idx, len(items)))
+ }
+ return items[ptr.Idx].Body.CloneItem()
+}
diff --git a/lib/btrfsutil/rebuilt_tree.go b/lib/btrfsutil/rebuilt_tree.go
new file mode 100644
index 0000000..39d8871
--- /dev/null
+++ b/lib/btrfsutil/rebuilt_tree.go
@@ -0,0 +1,357 @@
+// Copyright (C) 2022-2023 Luke Shumaker <lukeshu@lukeshu.com>
+//
+// SPDX-License-Identifier: GPL-2.0-or-later
+
+package btrees
+
+import (
+ "context"
+ "fmt"
+ "sync"
+ "time"
+
+ "github.com/datawire/dlib/dlog"
+
+ "git.lukeshu.com/btrfs-progs-ng/lib/btrfs/btrfsitem"
+ "git.lukeshu.com/btrfs-progs-ng/lib/btrfs/btrfsprim"
+ "git.lukeshu.com/btrfs-progs-ng/lib/btrfs/btrfsvol"
+ "git.lukeshu.com/btrfs-progs-ng/lib/btrfsprogs/btrfsinspect/rebuildnodes/keyio"
+ "git.lukeshu.com/btrfs-progs-ng/lib/containers"
+ "git.lukeshu.com/btrfs-progs-ng/lib/maps"
+ "git.lukeshu.com/btrfs-progs-ng/lib/slices"
+ "git.lukeshu.com/btrfs-progs-ng/lib/textui"
+)
+
+type RebuiltTree struct {
+ // static
+ ID btrfsprim.ObjID
+ UUID btrfsprim.UUID
+ Parent *RebuiltTree
+ ParentGen btrfsprim.Generation // offset of this tree's root item
+ forrest *RebuiltForrest
+
+ // mutable
+ mu sync.RWMutex
+ Roots containers.Set[btrfsvol.LogicalAddr]
+ // There are 3 more mutable "members" that are protected by
+ // `mu`; but they live in a shared LRUcache. They are all
+ // derived from tree.Roots, which is why it's OK if they get
+ // evicted.
+ //
+ // 1. tree.leafToRoots() = tree.forrest.leafs.Load(tree.ID)
+ // 2. tree.Items() = tree.forrest.incItems.Load(tree.ID)
+ // 3. tree.PotentialItems() = tree.forrest.excItems.Load(tree.ID)
+}
+
+// LRU member 1: .leafToRoots() ////////////////////////////////////////////////////////////////////////////////////////
+
+// 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 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])
+
+ var stats textui.Portion[int]
+ stats.D = len(tree.forrest.graph.Nodes)
+ progressWriter := textui.NewProgress[textui.Portion[int]](ctx, dlog.LogLevelInfo, textui.Tunable(1*time.Second))
+ progress := func() {
+ stats.N = len(nodeToRoots)
+ progressWriter.Set(stats)
+ }
+
+ progress()
+ for _, node := range maps.SortedKeys(tree.forrest.graph.Nodes) {
+ tree.indexNode(ctx, node, nodeToRoots, progress, nil)
+ }
+ progressWriter.Done()
+
+ ret := make(map[btrfsvol.LogicalAddr]containers.Set[btrfsvol.LogicalAddr])
+ for node, roots := range nodeToRoots {
+ if tree.forrest.graph.Nodes[node].Level == 0 && len(roots) > 0 {
+ ret[node] = roots
+ }
+ }
+ return ret
+ })
+}
+
+func (tree *RebuiltTree) indexNode(ctx context.Context, node btrfsvol.LogicalAddr, index map[btrfsvol.LogicalAddr]containers.Set[btrfsvol.LogicalAddr], progress func(), stack []btrfsvol.LogicalAddr) {
+ defer progress()
+ if err := ctx.Err(); err != nil {
+ return
+ }
+ if _, done := index[node]; done {
+ return
+ }
+ if slices.Contains(node, stack) {
+ // This is a panic because tree.forrest.graph.FinalCheck() should
+ // have already checked for loops.
+ panic("loop")
+ }
+ if !tree.isOwnerOK(tree.forrest.graph.Nodes[node].Owner, tree.forrest.graph.Nodes[node].Generation) {
+ index[node] = nil
+ return
+ }
+
+ // tree.leafToRoots
+ stack = append(stack, node)
+ var roots containers.Set[btrfsvol.LogicalAddr]
+ for _, kp := range tree.forrest.graph.EdgesTo[node] {
+ if !tree.isOwnerOK(tree.forrest.graph.Nodes[kp.FromNode].Owner, tree.forrest.graph.Nodes[kp.FromNode].Generation) {
+ continue
+ }
+ tree.indexNode(ctx, kp.FromNode, index, progress, stack)
+ if len(index[kp.FromNode]) > 0 {
+ if roots == nil {
+ roots = make(containers.Set[btrfsvol.LogicalAddr])
+ }
+ roots.InsertFrom(index[kp.FromNode])
+ }
+ }
+ if roots == nil {
+ roots = containers.NewSet[btrfsvol.LogicalAddr](node)
+ }
+ index[node] = roots
+}
+
+// isOwnerOK returns whether it is permissible for a node with
+// .Head.Owner=owner to be in this tree.
+func (tree *RebuiltTree) isOwnerOK(owner btrfsprim.ObjID, gen btrfsprim.Generation) bool {
+ for {
+ if owner == tree.ID {
+ return true
+ }
+ if tree.Parent == nil || gen >= tree.ParentGen {
+ return false
+ }
+ tree = tree.Parent
+ }
+}
+
+// LRU members 2 and 3: .Items() and .PotentialItems() /////////////////////////////////////////////////////////////////
+
+// Items returns a map of the items contained in this tree.
+//
+// Do not mutate the returned map; it is a pointer to the
+// 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)
+}
+
+// PotentialItems returns a map of items that could be added to this
+// tree with .AddRoot().
+//
+// Do not mutate the returned map; it is a pointer to the
+// 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,
+ func(roots containers.Set[btrfsvol.LogicalAddr]) bool {
+ return !tree.Roots.HasAny(roots)
+ })
+}
+
+type itemIndex = containers.SortedMap[btrfsprim.Key, keyio.ItemPtr]
+
+type itemStats struct {
+ Leafs textui.Portion[int]
+ NumItems int
+ NumDups int
+}
+
+func (s itemStats) String() string {
+ return textui.Sprintf("%v (%v items, %v dups)",
+ s.Leafs, s.NumItems, s.NumDups)
+}
+
+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 containers.LoadOrElse(cache, tree.ID, func(btrfsprim.ObjID) *itemIndex {
+ var leafs []btrfsvol.LogicalAddr
+ for leaf, roots := range tree.leafToRoots(ctx) {
+ if leafFn(roots) {
+ leafs = append(leafs, leaf)
+ }
+ }
+ slices.Sort(leafs)
+
+ var stats itemStats
+ stats.Leafs.D = len(leafs)
+ progressWriter := textui.NewProgress[itemStats](ctx, dlog.LogLevelInfo, textui.Tunable(1*time.Second))
+
+ index := new(containers.SortedMap[btrfsprim.Key, keyio.ItemPtr])
+ for i, leaf := range leafs {
+ stats.Leafs.N = i
+ progressWriter.Set(stats)
+ for j, itemKey := range tree.forrest.graph.Nodes[leaf].Items {
+ newPtr := keyio.ItemPtr{
+ Node: leaf,
+ Idx: j,
+ }
+ if oldPtr, exists := index.Load(itemKey); !exists {
+ index.Store(itemKey, newPtr)
+ stats.NumItems++
+ } else {
+ if tree.ShouldReplace(oldPtr.Node, newPtr.Node) {
+ index.Store(itemKey, newPtr)
+ }
+ stats.NumDups++
+ }
+ progressWriter.Set(stats)
+ }
+ }
+ if stats.Leafs.N > 0 {
+ stats.Leafs.N = len(leafs)
+ progressWriter.Set(stats)
+ progressWriter.Done()
+ }
+
+ return index
+ })
+}
+
+func (tree *RebuiltTree) ShouldReplace(oldNode, newNode btrfsvol.LogicalAddr) bool {
+ oldDist, _ := tree.COWDistance(tree.forrest.graph.Nodes[oldNode].Owner)
+ newDist, _ := tree.COWDistance(tree.forrest.graph.Nodes[newNode].Owner)
+ switch {
+ case newDist < oldDist:
+ // Replace the old one with the new lower-dist one.
+ return true
+ case newDist > oldDist:
+ // Retain the old lower-dist one.
+ return false
+ default:
+ oldGen := tree.forrest.graph.Nodes[oldNode].Generation
+ newGen := tree.forrest.graph.Nodes[newNode].Generation
+ switch {
+ case newGen > oldGen:
+ // Replace the old one with the new higher-gen one.
+ return true
+ case newGen < oldGen:
+ // Retain the old higher-gen one.
+ return false
+ default:
+ // TODO: 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 nodes in tree=%v: old=%v=%v ; new=%v=%v",
+ tree.ID,
+ oldNode, tree.forrest.graph.Nodes[oldNode],
+ newNode, tree.forrest.graph.Nodes[newNode]))
+ }
+ }
+}
+
+// .AddRoot() //////////////////////////////////////////////////////////////////////////////////////////////////////////
+
+type rootStats struct {
+ Leafs textui.Portion[int]
+ AddedLeafs int
+ AddedItems int
+}
+
+func (s rootStats) String() string {
+ return textui.Sprintf("%v (added %v leafs, added %v items)",
+ s.Leafs, s.AddedLeafs, s.AddedItems)
+}
+
+// AddRoot adds an additional root node to the tree. It is useful to
+// call .AddRoot() to re-attach part of the tree that has been broken
+// off.
+func (tree *RebuiltTree) AddRoot(ctx context.Context, rootNode btrfsvol.LogicalAddr) {
+ tree.mu.Lock()
+ defer tree.mu.Unlock()
+ ctx = dlog.WithField(ctx, "btrfsinspect.rebuild-nodes.rebuild.add-root", fmt.Sprintf("tree=%v rootNode=%v", tree.ID, rootNode))
+ dlog.Info(ctx, "adding root...")
+
+ leafToRoots := tree.leafToRoots(ctx)
+
+ var stats rootStats
+ stats.Leafs.D = len(leafToRoots)
+ progressWriter := textui.NewProgress[rootStats](ctx, dlog.LogLevelInfo, textui.Tunable(1*time.Second))
+ for i, leaf := range maps.SortedKeys(leafToRoots) {
+ stats.Leafs.N = i
+ progressWriter.Set(stats)
+
+ if tree.Roots.HasAny(leafToRoots[leaf]) || !leafToRoots[leaf].Has(rootNode) {
+ continue
+ }
+
+ stats.AddedLeafs++
+ progressWriter.Set(stats)
+
+ for _, itemKey := range tree.forrest.graph.Nodes[leaf].Items {
+ tree.forrest.cb.AddedItem(ctx, tree.ID, itemKey)
+ stats.AddedItems++
+ progressWriter.Set(stats)
+ }
+ }
+ stats.Leafs.N = len(leafToRoots)
+ progressWriter.Set(stats)
+ progressWriter.Done()
+
+ tree.Roots.Insert(rootNode)
+ 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.flushNegativeCache(ctx)
+ }
+ tree.forrest.cb.AddedRoot(ctx, tree.ID, rootNode)
+}
+
+// main public API /////////////////////////////////////////////////////////////////////////////////////////////////////
+
+// COWDistance returns how many COW-snapshots down the 'tree' is from
+// the 'parent'.
+func (tree *RebuiltTree) COWDistance(parentID btrfsprim.ObjID) (dist int, ok bool) {
+ for {
+ if parentID == tree.ID {
+ return dist, true
+ }
+ if tree.Parent == nil {
+ return 0, false
+ }
+ tree = tree.Parent
+ dist++
+ }
+}
+
+// ReadItem reads an item from a tree.
+func (tree *RebuiltTree) ReadItem(ctx context.Context, key btrfsprim.Key) btrfsitem.Item {
+ ptr, ok := tree.Items(ctx).Load(key)
+ if !ok {
+ panic(fmt.Errorf("should not happen: btrees.RebuiltTree.ReadItem called for not-included key: %v", key))
+ }
+ return tree.forrest.keyIO.ReadItem(ctx, ptr)
+}
+
+// LeafToRoots returns the list of potential roots (to pass to
+// .AddRoot) that include a given leaf-node.
+func (tree *RebuiltTree) LeafToRoots(ctx context.Context, leaf btrfsvol.LogicalAddr) containers.Set[btrfsvol.LogicalAddr] {
+ if tree.forrest.graph.Nodes[leaf].Level != 0 {
+ panic(fmt.Errorf("should not happen: (tree=%v).LeafToRoots(leaf=%v): not a leaf",
+ tree.ID, leaf))
+ }
+ tree.mu.RLock()
+ defer tree.mu.RUnlock()
+ ret := make(containers.Set[btrfsvol.LogicalAddr])
+ for root := range tree.leafToRoots(ctx)[leaf] {
+ if tree.Roots.Has(root) {
+ panic(fmt.Errorf("should not happen: (tree=%v).LeafToRoots(leaf=%v): tree contains root=%v but not leaf",
+ tree.ID, leaf, root))
+ }
+ ret.Insert(root)
+ }
+ if len(ret) == 0 {
+ return nil
+ }
+ return ret
+}
diff --git a/lib/btrfsutil/skinny_paths.go b/lib/btrfsutil/skinny_paths.go
new file mode 100644
index 0000000..1695990
--- /dev/null
+++ b/lib/btrfsutil/skinny_paths.go
@@ -0,0 +1,146 @@
+// 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, itemIdx int) (btrfstree.TreePathElem, error) {
+ if itemIdx < 0 {
+ panic("should not happen")
+ }
+
+ a.init()
+
+ ret, ok := a.fatItems.Load(skinnyItem{
+ Node: parent.Node(-1).ToNodeAddr,
+ Item: itemIdx,
+ })
+ if ok {
+ return ret, nil
+ }
+
+ node, err := btrfstree.ReadNode(a.FS, a.SB, parent.Node(-1).ToNodeAddr, btrfstree.NodeExpectations{})
+ defer btrfstree.FreeNodeRef(node)
+ if err != nil {
+ return btrfstree.TreePathElem{}, err
+ }
+ if node.Data.Head.Level > 0 {
+ if itemIdx >= len(node.Data.BodyInternal) {
+ panic("should not happen")
+ }
+ for i, item := range node.Data.BodyInternal {
+ toMaxKey := parent.Node(-1).ToMaxKey
+ if i+1 < len(node.Data.BodyInternal) {
+ toMaxKey = node.Data.BodyInternal[i+1].Key.Mm()
+ }
+ elem := btrfstree.TreePathElem{
+ FromTree: node.Data.Head.Owner,
+ FromItemIdx: i,
+ ToNodeAddr: item.BlockPtr,
+ ToNodeGeneration: item.Generation,
+ ToNodeLevel: node.Data.Head.Level - 1,
+ ToKey: item.Key,
+ ToMaxKey: toMaxKey,
+ }
+ a.fatItems.Store(skinnyItem{Node: parent.Node(-1).ToNodeAddr, Item: i}, elem)
+ if i == itemIdx {
+ ret = elem
+ }
+ }
+ } else {
+ if itemIdx >= len(node.Data.BodyLeaf) {
+ panic("should not happen")
+ }
+ for i, item := range node.Data.BodyLeaf {
+ elem := btrfstree.TreePathElem{
+ FromTree: node.Data.Head.Owner,
+ FromItemIdx: i,
+ ToKey: item.Key,
+ ToMaxKey: item.Key,
+ }
+ a.fatItems.Store(skinnyItem{Node: parent.Node(-1).ToNodeAddr, Item: i}, elem)
+ if i == itemIdx {
+ 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.FromItemIdx}, elem)
+ ret.Items = append(ret.Items, elem.FromItemIdx)
+ }
+ 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 _, itemIdx := range skinny.Items {
+ elem, err := a.getItem(ret, itemIdx)
+ if err != nil {
+ panic(err)
+ }
+ ret = append(ret, elem)
+ }
+
+ return ret
+}
diff --git a/lib/btrfsutil/walk.go b/lib/btrfsutil/walk.go
new file mode 100644
index 0000000..355976a
--- /dev/null
+++ b/lib/btrfsutil/walk.go
@@ -0,0 +1,97 @@
+// Copyright (C) 2022 Luke Shumaker <lukeshu@lukeshu.com>
+//
+// SPDX-License-Identifier: GPL-2.0-or-later
+
+package btrfsutil
+
+import (
+ "context"
+ "fmt"
+
+ "git.lukeshu.com/btrfs-progs-ng/lib/btrfs/btrfsitem"
+ "git.lukeshu.com/btrfs-progs-ng/lib/btrfs/btrfsprim"
+ "git.lukeshu.com/btrfs-progs-ng/lib/btrfs/btrfstree"
+)
+
+type WalkError struct {
+ TreeName string
+ Err *btrfstree.TreeError
+}
+
+func (e *WalkError) Unwrap() error { return e.Err }
+
+func (e *WalkError) Error() string {
+ return fmt.Sprintf("%v: %v", e.TreeName, e.Err)
+}
+
+type WalkAllTreesHandler struct {
+ Err func(*WalkError)
+ // Callbacks for entire trees
+ PreTree func(name string, id btrfsprim.ObjID)
+ PostTree func(name string, id btrfsprim.ObjID)
+ // Callbacks for nodes or smaller
+ btrfstree.TreeWalkHandler
+}
+
+// WalkAllTrees walks all trees in a *btrfs.FS. Rather than returning
+// an error, it calls errCb each time an error is encountered. The
+// error will always be of type WalkError.
+func WalkAllTrees(ctx context.Context, fs btrfstree.TreeOperator, cbs WalkAllTreesHandler) {
+ var treeName string
+
+ trees := []struct {
+ Name string
+ ID btrfsprim.ObjID
+ }{
+ {
+ Name: "root tree",
+ ID: btrfsprim.ROOT_TREE_OBJECTID,
+ },
+ {
+ Name: "chunk tree",
+ ID: btrfsprim.CHUNK_TREE_OBJECTID,
+ },
+ {
+ Name: "log tree",
+ ID: btrfsprim.TREE_LOG_OBJECTID,
+ },
+ {
+ Name: "block group tree",
+ ID: btrfsprim.BLOCK_GROUP_TREE_OBJECTID,
+ },
+ }
+ origItem := cbs.Item
+ cbs.Item = func(path btrfstree.TreePath, item btrfstree.Item) error {
+ if item.Key.ItemType == btrfsitem.ROOT_ITEM_KEY {
+ trees = append(trees, struct {
+ Name string
+ ID btrfsprim.ObjID
+ }{
+ Name: fmt.Sprintf("tree %v (via %v %v)",
+ item.Key.ObjectID.Format(0), treeName, path),
+ ID: item.Key.ObjectID,
+ })
+ }
+ if origItem != nil {
+ return origItem(path, item)
+ }
+ return nil
+ }
+
+ for i := 0; i < len(trees); i++ {
+ tree := trees[i]
+ treeName = tree.Name
+ if cbs.PreTree != nil {
+ cbs.PreTree(treeName, tree.ID)
+ }
+ fs.TreeWalk(
+ ctx,
+ tree.ID,
+ func(err *btrfstree.TreeError) { cbs.Err(&WalkError{TreeName: treeName, Err: err}) },
+ cbs.TreeWalkHandler,
+ )
+ if cbs.PostTree != nil {
+ cbs.PostTree(treeName, tree.ID)
+ }
+ }
+}
generated by cgit v1.2.3-2-g168b (git 2.25.1) at 2024-07-15 07:06:15 +0000