diff options
Diffstat (limited to 'lib/btrfsutil')
-rw-r--r-- | lib/btrfsutil/graph.go | 262 | ||||
-rw-r--r-- | lib/btrfsutil/graph_loops.go | 133 | ||||
-rw-r--r-- | lib/btrfsutil/nestedlock.go | 45 | ||||
-rw-r--r-- | lib/btrfsutil/old_rebuilt_forrest.go | 358 | ||||
-rw-r--r-- | lib/btrfsutil/open.go | 46 | ||||
-rw-r--r-- | lib/btrfsutil/print_addrspace.go | 73 | ||||
-rw-r--r-- | lib/btrfsutil/rebuilt_forrest.go | 206 | ||||
-rw-r--r-- | lib/btrfsutil/rebuilt_readitem.go | 171 | ||||
-rw-r--r-- | lib/btrfsutil/rebuilt_tree.go | 356 | ||||
-rw-r--r-- | lib/btrfsutil/skinny_paths.go | 146 | ||||
-rw-r--r-- | lib/btrfsutil/walk.go | 97 |
11 files changed, 1893 insertions, 0 deletions
diff --git a/lib/btrfsutil/graph.go b/lib/btrfsutil/graph.go new file mode 100644 index 0000000..8debe9d --- /dev/null +++ b/lib/btrfsutil/graph.go @@ -0,0 +1,262 @@ +// Copyright (C) 2022-2023 Luke Shumaker <lukeshu@lukeshu.com> +// +// SPDX-License-Identifier: GPL-2.0-or-later + +package btrfsutil + +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 GraphNode struct { + Level uint8 + Generation btrfsprim.Generation + Owner btrfsprim.ObjID + NumItems uint32 + MinItem btrfsprim.Key + MaxItem btrfsprim.Key + Items []btrfsprim.Key +} + +func (n GraphNode) 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 GraphEdge struct { + // It is invalid for both 'FromRoot' and 'FromNode' to be + // non-zero. If both are zero, then the GraphEdge 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 GraphEdge) 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]GraphNode + BadNodes map[btrfsvol.LogicalAddr]error + EdgesFrom map[btrfsvol.LogicalAddr][]*GraphEdge + EdgesTo map[btrfsvol.LogicalAddr][]*GraphEdge +} + +func (g Graph) insertEdge(ptr *GraphEdge) { + 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(&GraphEdge{ + FromTree: treeID, + ToNode: treeInfo.RootNode, + ToLevel: treeInfo.Level, + ToGeneration: treeInfo.Generation, + }) +} + +func NewGraph(sb btrfstree.Superblock) *Graph { + g := &Graph{ + Nodes: make(map[btrfsvol.LogicalAddr]GraphNode), + BadNodes: make(map[btrfsvol.LogicalAddr]error), + EdgesFrom: make(map[btrfsvol.LogicalAddr][]*GraphEdge), + EdgesTo: make(map[btrfsvol.LogicalAddr][]*GraphEdge), + } + + // 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 := GraphNode{ + 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([]GraphEdge, 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, GraphEdge{ + 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([]GraphEdge, len(nodeRef.Data.BodyInternal)) + for i, kp := range nodeRef.Data.BodyInternal { + kps[i] = GraphEdge{ + 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] + + 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") + + 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..3382705 --- /dev/null +++ b/lib/btrfsutil/graph_loops.go @@ -0,0 +1,133 @@ +// Copyright (C) 2022-2023 Luke Shumaker <lukeshu@lukeshu.com> +// +// SPDX-License-Identifier: GPL-2.0-or-later + +package btrfsutil + +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 GraphEdge) []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 GraphEdge, toNode GraphNode) 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..917b4cd --- /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 btrfsutil + +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..2386803 --- /dev/null +++ b/lib/btrfsutil/old_rebuilt_forrest.go @@ -0,0 +1,358 @@ +// 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 oldRebuiltTree struct { + RootErr error + Items *containers.RBTree[oldRebuiltTreeValue] + Errors *containers.IntervalTree[btrfsprim.Key, oldRebuiltTreeError] +} + +type oldRebuiltTreeError struct { + Path SkinnyPath + Err error +} + +type oldRebuiltTreeValue struct { + Path SkinnyPath + Key btrfsprim.Key + ItemSize uint32 +} + +// Compare implements containers.Ordered. +func (a oldRebuiltTreeValue) Compare(b oldRebuiltTreeValue) int { + return a.Key.Compare(b.Key) +} + +func newOldRebuiltTree(arena *SkinnyPathArena) oldRebuiltTree { + return oldRebuiltTree{ + Items: new(containers.RBTree[oldRebuiltTreeValue]), + Errors: &containers.IntervalTree[btrfsprim.Key, oldRebuiltTreeError]{ + MinFn: func(err oldRebuiltTreeError) btrfsprim.Key { + return arena.Inflate(err.Path).Node(-1).ToKey + }, + MaxFn: func(err oldRebuiltTreeError) btrfsprim.Key { + return arena.Inflate(err.Path).Node(-1).ToMaxKey + }, + }, + } +} + +type OldRebuiltForrest 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 + rootTree *oldRebuiltTree + // for all other trees + treesMu sync.Mutex + trees map[btrfsprim.ObjID]oldRebuiltTree +} + +var _ btrfstree.TreeOperator = (*OldRebuiltForrest)(nil) + +// NewOldRebuiltForrest 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. +// +// NewOldRebuiltForrest 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 NewOldRebuiltForrest(ctx context.Context, inner *btrfs.FS) *OldRebuiltForrest { + return &OldRebuiltForrest{ + ctx: ctx, + inner: inner, + } +} + +func (bt *OldRebuiltForrest) RebuiltTree(treeID btrfsprim.ObjID) oldRebuiltTree { + 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.rootTree != nil { + return *bt.rootTree + } + sb, err = bt.inner.Superblock() + if err == nil { + treeRoot, err = btrfstree.LookupTreeRoot(bt.inner, *sb, treeID) + } + } else { + bt.treesMu.Lock() + defer bt.treesMu.Unlock() + if bt.trees == nil { + bt.trees = make(map[btrfsprim.ObjID]oldRebuiltTree) + } + if cacheEntry, exists := bt.trees[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 := newOldRebuiltTree(bt.arena) + if err != nil { + cacheEntry.RootErr = 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.rootTree = &cacheEntry + } else { + bt.trees[treeID] = cacheEntry + } + return cacheEntry +} + +func (bt *OldRebuiltForrest) rawTreeWalk(root btrfstree.TreeRoot, cacheEntry oldRebuiltTree, 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(oldRebuiltTreeError{ + 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 oldRebuiltTreeValue) 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(oldRebuiltTreeValue{ + Path: bt.arena.Deflate(path), + Key: item.Key, + ItemSize: item.BodySize, + }) + if walked != nil { + *walked = append(*walked, item.Key) + } + return nil + }, + }, + ) +} + +func (bt *OldRebuiltForrest) 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 *OldRebuiltForrest) addErrs(tree oldRebuiltTree, fn func(btrfsprim.Key, uint32) int, err error) error { + var errs derror.MultiError + tree.Errors.Subrange( + func(k btrfsprim.Key) int { return fn(k, 0) }, + func(v oldRebuiltTreeError) 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 *OldRebuiltForrest) TreeSearch(treeID btrfsprim.ObjID, fn func(btrfsprim.Key, uint32) int) (btrfstree.Item, error) { + tree := bt.RebuiltTree(treeID) + if tree.RootErr != nil { + return btrfstree.Item{}, tree.RootErr + } + + indexItem := tree.Items.Search(func(indexItem oldRebuiltTreeValue) int { + return fn(indexItem.Key, indexItem.ItemSize) + }) + if indexItem == nil { + return btrfstree.Item{}, bt.addErrs(tree, 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(tree, 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 *OldRebuiltForrest) TreeSearchAll(treeID btrfsprim.ObjID, fn func(btrfsprim.Key, uint32) int) ([]btrfstree.Item, error) { + tree := bt.RebuiltTree(treeID) + if tree.RootErr != nil { + return nil, tree.RootErr + } + + var indexItems []oldRebuiltTreeValue + tree.Items.Subrange( + func(indexItem oldRebuiltTreeValue) int { return fn(indexItem.Key, indexItem.ItemSize) }, + func(node *containers.RBNode[oldRebuiltTreeValue]) bool { + indexItems = append(indexItems, node.Value) + return true + }) + if len(indexItems) == 0 { + return nil, bt.addErrs(tree, 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(tree, 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(tree, fn, nil) +} + +func (bt *OldRebuiltForrest) TreeWalk(ctx context.Context, treeID btrfsprim.ObjID, errHandle func(*btrfstree.TreeError), cbs btrfstree.TreeWalkHandler) { + tree := bt.RebuiltTree(treeID) + if tree.RootErr != nil { + errHandle(&btrfstree.TreeError{ + Path: btrfstree.TreePath{{ + FromTree: treeID, + ToMaxKey: btrfsprim.MaxKey, + }}, + Err: tree.RootErr, + }) + return + } + var node *diskio.Ref[btrfsvol.LogicalAddr, btrfstree.Node] + tree.Items.Range(func(indexItem *containers.RBNode[oldRebuiltTreeValue]) 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 *OldRebuiltForrest) Superblock() (*btrfstree.Superblock, error) { + return bt.inner.Superblock() +} + +func (bt *OldRebuiltForrest) ReadAt(p []byte, off btrfsvol.LogicalAddr) (int, error) { + return bt.inner.ReadAt(p, off) +} + +func (bt *OldRebuiltForrest) Augment(treeID btrfsprim.ObjID, nodeAddr btrfsvol.LogicalAddr) ([]btrfsprim.Key, error) { + sb, err := bt.Superblock() + if err != nil { + return nil, err + } + tree := bt.RebuiltTree(treeID) + if tree.RootErr != nil { + return nil, tree.RootErr + } + 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, + }, tree, &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..c9c51f0 --- /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 btrfsutil + +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..70ece13 --- /dev/null +++ b/lib/btrfsutil/rebuilt_forrest.go @@ -0,0 +1,206 @@ +// Copyright (C) 2022-2023 Luke Shumaker <lukeshu@lukeshu.com> +// +// SPDX-License-Identifier: GPL-2.0-or-later + +package btrfsutil + +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" + "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 RebuiltForrestCallbacks 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 OldRebuiltForrest. However, the API is +// different than btrfstree.TreeOperator, and is much more efficient +// than OldRebuiltForrest. +// +// The efficiency improvements are possible because of the API +// differences, which are necessary for how it is used in +// rebuildtrees: +// +// - it consumes an already-read 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 OldRebuiltForrest +// 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 Graph + keyIO *KeyIO + cb RebuiltForrestCallbacks + + // 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 Graph, keyIO *KeyIO, cb RebuiltForrestCallbacks) *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, "btrfs.util.rebuilt-forrest.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..57440cf --- /dev/null +++ b/lib/btrfsutil/rebuilt_readitem.go @@ -0,0 +1,171 @@ +// Copyright (C) 2022-2023 Luke Shumaker <lukeshu@lukeshu.com> +// +// SPDX-License-Identifier: GPL-2.0-or-later + +package btrfsutil + +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/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 KeyIO struct { + rawFile diskio.File[btrfsvol.LogicalAddr] + sb btrfstree.Superblock + 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 NewKeyIO(file diskio.File[btrfsvol.LogicalAddr], sb btrfstree.Superblock) *KeyIO { + return &KeyIO{ + 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 *KeyIO) 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 *KeyIO) SetGraph(graph Graph) { + o.graph = graph +} + +func (o *KeyIO) 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 *KeyIO) 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: btrfsutil.KeyIO.ReadItem called for non-leaf node@%v", ptr.Node)) + } + if ptr.Idx < 0 { + panic(fmt.Errorf("should not happen: btrfsutil.KeyIO.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: btrfsutil.KeyIO.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..1009204 --- /dev/null +++ b/lib/btrfsutil/rebuilt_tree.go @@ -0,0 +1,356 @@ +// Copyright (C) 2022-2023 Luke Shumaker <lukeshu@lukeshu.com> +// +// SPDX-License-Identifier: GPL-2.0-or-later + +package btrfsutil + +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/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, "btrfs.util.rebuilt-tree.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, ItemPtr] { + ctx = dlog.WithField(ctx, "btrfs.util.rebuilt-tree.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, ItemPtr] { + ctx = dlog.WithField(ctx, "btrfs.util.rebuilt-tree.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, 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, 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, ItemPtr]) + for i, leaf := range leafs { + stats.Leafs.N = i + progressWriter.Set(stats) + for j, itemKey := range tree.forrest.graph.Nodes[leaf].Items { + newPtr := 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, "btrfs.util.rebuilt-tree.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: btrfsutil.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) + } + } +} |