From aebdf099d1b02394debd71a40b18050370ba7416 Mon Sep 17 00:00:00 2001 From: Luke Shumaker Date: Sun, 18 Dec 2022 00:58:08 -0700 Subject: rebuildnodes: Optimize memory access when indexing orphans --- .../btrfsinspect/rebuildnodes/graph/graph.go | 69 +++++++++++++--------- 1 file changed, 41 insertions(+), 28 deletions(-) (limited to 'lib/btrfsprogs/btrfsinspect/rebuildnodes/graph/graph.go') diff --git a/lib/btrfsprogs/btrfsinspect/rebuildnodes/graph/graph.go b/lib/btrfsprogs/btrfsinspect/rebuildnodes/graph/graph.go index 7ae3b89..0a24588 100644 --- a/lib/btrfsprogs/btrfsinspect/rebuildnodes/graph/graph.go +++ b/lib/btrfsprogs/btrfsinspect/rebuildnodes/graph/graph.go @@ -51,13 +51,12 @@ type Graph struct { EdgesTo map[btrfsvol.LogicalAddr][]*Edge } -func (g Graph) insertEdge(kp Edge) { - ptr := &kp - if kp.ToNode == 0 { +func (g Graph) insertEdge(ptr *Edge) { + if ptr.ToNode == 0 { panic("kp.ToNode should not be zero") } - g.EdgesFrom[kp.FromNode] = append(g.EdgesFrom[kp.FromNode], ptr) - g.EdgesTo[kp.ToNode] = append(g.EdgesTo[kp.ToNode], ptr) + 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) { @@ -72,7 +71,7 @@ func (g Graph) insertTreeRoot(sb btrfstree.Superblock, treeID btrfsprim.ObjID) { if treeInfo.RootNode == 0 { return } - g.insertEdge(Edge{ + g.insertEdge(&Edge{ FromTree: treeID, ToNode: treeInfo.RootNode, ToLevel: treeInfo.Level, @@ -99,18 +98,6 @@ func New(sb btrfstree.Superblock) *Graph { } func (g *Graph) InsertNode(nodeRef *diskio.Ref[btrfsvol.LogicalAddr, btrfstree.Node]) { - for _, item := range nodeRef.Data.BodyLeaf { - switch itemBody := item.Body.(type) { - case btrfsitem.Root: - g.insertEdge(Edge{ - FromTree: item.Key.ObjectID, - ToNode: itemBody.ByteNr, - ToLevel: itemBody.Level, - ToGeneration: itemBody.Generation, - }) - } - } - g.Nodes[nodeRef.Addr] = Node{ Level: nodeRef.Data.Head.Level, Generation: nodeRef.Data.Head.Generation, @@ -119,16 +106,42 @@ func (g *Graph) InsertNode(nodeRef *diskio.Ref[btrfsvol.LogicalAddr, btrfstree.N MinItem: discardOK(nodeRef.Data.MinItem()), MaxItem: discardOK(nodeRef.Data.MaxItem()), } - for i, kp := range nodeRef.Data.BodyInternal { - g.insertEdge(Edge{ - FromTree: nodeRef.Data.Head.Owner, - FromNode: nodeRef.Addr, - FromItem: i, - ToNode: kp.BlockPtr, - ToLevel: nodeRef.Data.Head.Level - 1, - ToKey: kp.Key, - ToGeneration: kp.Generation, - }) + + if nodeRef.Data.Head.Level == 0 { + cnt := 0 + for _, item := range nodeRef.Data.BodyLeaf { + switch item.Body.(type) { + case btrfsitem.Root: + cnt++ + } + } + kps := make([]Edge, 0, cnt) + for _, item := range nodeRef.Data.BodyLeaf { + switch itemBody := item.Body.(type) { + case btrfsitem.Root: + kps = append(kps, Edge{ + FromTree: item.Key.ObjectID, + ToNode: itemBody.ByteNr, + ToLevel: itemBody.Level, + ToGeneration: itemBody.Generation, + }) + g.insertEdge(&kps[len(kps)-1]) + } + } + } else { + kps := make([]Edge, len(nodeRef.Data.BodyInternal)) + for i, kp := range nodeRef.Data.BodyInternal { + kps[i] = Edge{ + FromTree: nodeRef.Data.Head.Owner, + FromNode: nodeRef.Addr, + FromItem: i, + ToNode: kp.BlockPtr, + ToLevel: nodeRef.Data.Head.Level - 1, + ToKey: kp.Key, + ToGeneration: kp.Generation, + } + g.insertEdge(&kps[i]) + } } } -- cgit v1.2.3-2-g168b From 15f0adbfccdf8e4be9f6f493ef5b1fd6bce1488f Mon Sep 17 00:00:00 2001 From: Luke Shumaker Date: Tue, 20 Dec 2022 03:09:23 -0700 Subject: rebuildnodes/graph: Track root items, improve string representations --- .../btrfsinspect/rebuildnodes/graph/graph.go | 52 +++++++++++++++++----- 1 file changed, 42 insertions(+), 10 deletions(-) (limited to 'lib/btrfsprogs/btrfsinspect/rebuildnodes/graph/graph.go') diff --git a/lib/btrfsprogs/btrfsinspect/rebuildnodes/graph/graph.go b/lib/btrfsprogs/btrfsinspect/rebuildnodes/graph/graph.go index 0a24588..46fb4b2 100644 --- a/lib/btrfsprogs/btrfsinspect/rebuildnodes/graph/graph.go +++ b/lib/btrfsprogs/btrfsinspect/rebuildnodes/graph/graph.go @@ -24,10 +24,25 @@ type Node struct { MaxItem btrfsprim.Key } +func (n Node) String() string { + if n == (Node{}) { + 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 { - FromTree btrfsprim.ObjID + // It is invalid 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 + FromItem int // only valid if one of FromRoot or FromNode is non-zero + + FromTree btrfsprim.ObjID ToNode btrfsvol.LogicalAddr ToLevel uint8 @@ -36,8 +51,19 @@ type Edge struct { } func (kp Edge) String() string { - return fmt.Sprintf(`{t:%v,n:%v}[%d]->{n:%v,l:%v,g:%v,k:(%d,%v,%d)}`, - kp.FromTree, kp.FromNode, kp.FromItem, + 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, @@ -55,6 +81,12 @@ 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) } @@ -110,16 +142,16 @@ func (g *Graph) InsertNode(nodeRef *diskio.Ref[btrfsvol.LogicalAddr, btrfstree.N if nodeRef.Data.Head.Level == 0 { cnt := 0 for _, item := range nodeRef.Data.BodyLeaf { - switch item.Body.(type) { - case btrfsitem.Root: + if _, ok := item.Body.(btrfsitem.Root); ok { cnt++ } } kps := make([]Edge, 0, cnt) - for _, item := range nodeRef.Data.BodyLeaf { - switch itemBody := item.Body.(type) { - case btrfsitem.Root: + for i, item := range nodeRef.Data.BodyLeaf { + 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, @@ -132,9 +164,9 @@ func (g *Graph) InsertNode(nodeRef *diskio.Ref[btrfsvol.LogicalAddr, btrfstree.N kps := make([]Edge, len(nodeRef.Data.BodyInternal)) for i, kp := range nodeRef.Data.BodyInternal { kps[i] = Edge{ - FromTree: nodeRef.Data.Head.Owner, FromNode: nodeRef.Addr, FromItem: i, + FromTree: nodeRef.Data.Head.Owner, ToNode: kp.BlockPtr, ToLevel: nodeRef.Data.Head.Level - 1, ToKey: kp.Key, -- cgit v1.2.3-2-g168b From 8fc3c78924da1dedd3adce3b923adf58e5ca732a Mon Sep 17 00:00:00 2001 From: Luke Shumaker Date: Fri, 23 Dec 2022 17:50:46 -0700 Subject: rebuildnodes: Have the graph store keys; avoid I/O when indexing a tree --- lib/btrfsprogs/btrfsinspect/rebuildnodes/graph/graph.go | 11 +++++++++-- 1 file changed, 9 insertions(+), 2 deletions(-) (limited to 'lib/btrfsprogs/btrfsinspect/rebuildnodes/graph/graph.go') diff --git a/lib/btrfsprogs/btrfsinspect/rebuildnodes/graph/graph.go b/lib/btrfsprogs/btrfsinspect/rebuildnodes/graph/graph.go index 46fb4b2..1180b0d 100644 --- a/lib/btrfsprogs/btrfsinspect/rebuildnodes/graph/graph.go +++ b/lib/btrfsprogs/btrfsinspect/rebuildnodes/graph/graph.go @@ -6,6 +6,7 @@ package graph import ( "fmt" + "reflect" "git.lukeshu.com/btrfs-progs-ng/lib/btrfs/btrfsitem" "git.lukeshu.com/btrfs-progs-ng/lib/btrfs/btrfsprim" @@ -22,10 +23,11 @@ type Node struct { NumItems uint32 MinItem btrfsprim.Key MaxItem btrfsprim.Key + Items []btrfsprim.Key } func (n Node) String() string { - if n == (Node{}) { + 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)}`, @@ -130,7 +132,7 @@ func New(sb btrfstree.Superblock) *Graph { } func (g *Graph) InsertNode(nodeRef *diskio.Ref[btrfsvol.LogicalAddr, btrfstree.Node]) { - g.Nodes[nodeRef.Addr] = Node{ + nodeData := Node{ Level: nodeRef.Data.Head.Level, Generation: nodeRef.Data.Head.Generation, Owner: nodeRef.Data.Head.Owner, @@ -147,7 +149,11 @@ func (g *Graph) InsertNode(nodeRef *diskio.Ref[btrfsvol.LogicalAddr, btrfstree.N } } 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, @@ -161,6 +167,7 @@ func (g *Graph) InsertNode(nodeRef *diskio.Ref[btrfsvol.LogicalAddr, btrfstree.N } } } else { + g.Nodes[nodeRef.Addr] = nodeData kps := make([]Edge, len(nodeRef.Data.BodyInternal)) for i, kp := range nodeRef.Data.BodyInternal { kps[i] = Edge{ -- cgit v1.2.3-2-g168b