diff options
Diffstat (limited to 'lib/btrfsprogs/btrfsinspect/rebuildnodes/graph')
-rw-r--r-- | lib/btrfsprogs/btrfsinspect/rebuildnodes/graph/graph.go | 265 | ||||
-rw-r--r-- | lib/btrfsprogs/btrfsinspect/rebuildnodes/graph/loops.go | 133 |
2 files changed, 0 insertions, 398 deletions
diff --git a/lib/btrfsprogs/btrfsinspect/rebuildnodes/graph/graph.go b/lib/btrfsprogs/btrfsinspect/rebuildnodes/graph/graph.go deleted file mode 100644 index 2a97ec8..0000000 --- a/lib/btrfsprogs/btrfsinspect/rebuildnodes/graph/graph.go +++ /dev/null @@ -1,265 +0,0 @@ -// 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/btrfsprogs/btrfsinspect/rebuildnodes/graph/loops.go b/lib/btrfsprogs/btrfsinspect/rebuildnodes/graph/loops.go deleted file mode 100644 index 0e51805..0000000 --- a/lib/btrfsprogs/btrfsinspect/rebuildnodes/graph/loops.go +++ /dev/null @@ -1,133 +0,0 @@ -// 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 -} |