From 20de3140073547344d159a65db1a7e5c90ef95e9 Mon Sep 17 00:00:00 2001 From: Luke Shumaker Date: Fri, 31 Mar 2023 17:40:36 -0600 Subject: =?UTF-8?q?btrfsutil:=20Graph:=20I=20missed=20.FromItem=20in=20the?= =?UTF-8?q?=20"item"=E2=86=92"slot"=20switch?= MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit --- lib/btrfsutil/graph.go | 14 +++++++------- 1 file changed, 7 insertions(+), 7 deletions(-) (limited to 'lib/btrfsutil/graph.go') diff --git a/lib/btrfsutil/graph.go b/lib/btrfsutil/graph.go index ea33be7..090ccf4 100644 --- a/lib/btrfsutil/graph.go +++ b/lib/btrfsutil/graph.go @@ -59,7 +59,7 @@ type GraphEdge struct { // superblock. FromRoot btrfsvol.LogicalAddr FromNode btrfsvol.LogicalAddr - FromItem int // only valid if one of FromRoot or FromNode is non-zero + FromSlot int // only valid if one of FromRoot or FromNode is non-zero FromTree btrfsprim.ObjID @@ -74,10 +74,10 @@ func (kp GraphEdge) String() string { switch { case kp.FromRoot != 0: from = fmt.Sprintf("root@%v[%d]:%v", - kp.FromRoot, kp.FromItem, kp.FromTree) + kp.FromRoot, kp.FromSlot, kp.FromTree) case kp.FromNode != 0: from = fmt.Sprintf("{node:%v, tree:%v}[%d]", - kp.FromNode, kp.FromTree, kp.FromItem) + kp.FromNode, kp.FromTree, kp.FromSlot) default: from = fmt.Sprintf("superblock:%v", kp.FromTree) } @@ -103,8 +103,8 @@ func (g Graph) insertEdge(ptr *GraphEdge) { 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") + if (ptr.FromRoot == 0 && ptr.FromNode == 0) && ptr.FromSlot != 0 { + panic("kp.FromSlot should only be set if either kp.FromRoot or kp.FromSlot is set") } g.EdgesFrom[ptr.FromNode] = append(g.EdgesFrom[ptr.FromNode], ptr) g.EdgesTo[ptr.ToNode] = append(g.EdgesTo[ptr.ToNode], ptr) @@ -171,7 +171,7 @@ func (g Graph) InsertNode(node *btrfstree.Node) { if itemBody, ok := item.Body.(*btrfsitem.Root); ok { kps = append(kps, GraphEdge{ FromRoot: node.Head.Addr, - FromItem: i, + FromSlot: i, FromTree: item.Key.ObjectID, ToNode: itemBody.ByteNr, ToLevel: itemBody.Level, @@ -186,7 +186,7 @@ func (g Graph) InsertNode(node *btrfstree.Node) { for i, kp := range node.BodyInterior { kps[i] = GraphEdge{ FromNode: node.Head.Addr, - FromItem: i, + FromSlot: i, FromTree: node.Head.Owner, ToNode: kp.BlockPtr, ToLevel: node.Head.Level - 1, -- cgit v1.2.3-2-g168b From 74a82894df9bdef19d321611255b7923f9f25aff Mon Sep 17 00:00:00 2001 From: Luke Shumaker Date: Sun, 2 Apr 2023 18:36:11 -0600 Subject: btrfsutil: GraphNode: Have .MinItem and .MaxItem work on interior nodes too --- lib/btrfsutil/graph.go | 39 +++++++++++++++++++++++++++++---------- 1 file changed, 29 insertions(+), 10 deletions(-) (limited to 'lib/btrfsutil/graph.go') diff --git a/lib/btrfsutil/graph.go b/lib/btrfsutil/graph.go index 090ccf4..fe7fe70 100644 --- a/lib/btrfsutil/graph.go +++ b/lib/btrfsutil/graph.go @@ -23,34 +23,52 @@ import ( ) type GraphNode struct { + Addr btrfsvol.LogicalAddr Level uint8 Generation btrfsprim.Generation Owner btrfsprim.ObjID Items []btrfsprim.Key } -func (n GraphNode) MinItem() btrfsprim.Key { - if len(n.Items) == 0 { +func (n GraphNode) NumItems(g Graph) int { + switch n.Level { + case 0: + return len(n.Items) + default: + return len(g.EdgesFrom[n.Addr]) + } +} + +func (n GraphNode) MinItem(g Graph) btrfsprim.Key { + if n.NumItems(g) == 0 { return btrfsprim.Key{} } - return n.Items[0] + switch n.Level { + case 0: + return n.Items[0] + default: + return g.EdgesFrom[n.Addr][0].ToKey + } } -func (n GraphNode) MaxItem() btrfsprim.Key { - if len(n.Items) == 0 { +func (n GraphNode) MaxItem(g Graph) btrfsprim.Key { + if n.NumItems(g) == 0 { return btrfsprim.Key{} } - return n.Items[len(n.Items)-1] + switch n.Level { + case 0: + return n.Items[len(n.Items)-1] + default: + return g.EdgesFrom[n.Addr][len(g.EdgesFrom[n.Addr])-1].ToKey + } } 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, len(n.Items), - n.MinItem().ObjectID, n.MinItem().ItemType, n.MinItem().Offset, - n.MaxItem().ObjectID, n.MaxItem().ItemType, n.MaxItem().Offset) + return fmt.Sprintf(`{lvl:%v, gen:%v, tree:%v, cnt:%v}`, + n.Level, n.Generation, n.Owner, len(n.Items)) } type GraphEdge struct { @@ -150,6 +168,7 @@ func NewGraph(ctx context.Context, sb btrfstree.Superblock) Graph { func (g Graph) InsertNode(node *btrfstree.Node) { nodeData := GraphNode{ + Addr: node.Head.Addr, Level: node.Head.Level, Generation: node.Head.Generation, Owner: node.Head.Owner, -- cgit v1.2.3-2-g168b