From e46cbc7ee7f3a2b93bd1bdf02e1eb95b98100f57 Mon Sep 17 00:00:00 2001 From: Luke Shumaker Date: Tue, 28 Feb 2023 13:10:16 -0700 Subject: misc: btrfsutil: Shrink the size of GraphNode --- lib/btrfsutil/graph.go | 30 +++++++++++++++++------------- lib/btrfsutil/graph_loops.go | 21 +++++++++++---------- lib/btrfsutil/rebuilt_readitem.go | 4 ++-- 3 files changed, 30 insertions(+), 25 deletions(-) (limited to 'lib') diff --git a/lib/btrfsutil/graph.go b/lib/btrfsutil/graph.go index 8debe9d..9e453eb 100644 --- a/lib/btrfsutil/graph.go +++ b/lib/btrfsutil/graph.go @@ -27,20 +27,31 @@ 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) MinItem() btrfsprim.Key { + if len(n.Items) == 0 { + return btrfsprim.Key{} + } + return n.Items[0] +} + +func (n GraphNode) MaxItem() btrfsprim.Key { + if len(n.Items) == 0 { + return btrfsprim.Key{} + } + return n.Items[len(n.Items)-1] +} + 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) + 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) } type GraphEdge struct { @@ -143,9 +154,6 @@ func (g Graph) InsertNode(nodeRef *diskio.Ref[btrfsvol.LogicalAddr, btrfstree.No 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 { @@ -256,7 +264,3 @@ func (g Graph) FinalCheck(ctx context.Context, fs diskio.File[btrfsvol.LogicalAd 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 index 3382705..b5690af 100644 --- a/lib/btrfsutil/graph_loops.go +++ b/lib/btrfsutil/graph_loops.go @@ -22,15 +22,15 @@ func (g Graph) renderNode(node btrfsvol.LogicalAddr) []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(" num_items: %v,", len(nodeData.Items)), fmt.Sprintf(" min_item: {%d,%v,%d},", - nodeData.MinItem.ObjectID, - nodeData.MinItem.ItemType, - nodeData.MinItem.Offset), + 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), + nodeData.MaxItem().ObjectID, + nodeData.MaxItem().ItemType, + nodeData.MaxItem().Offset), } } else if nodeErr, ok := g.BadNodes[node]; ok { return []string{ @@ -120,11 +120,12 @@ func checkNodeExpectations(kp GraphEdge, toNode GraphNode) error { errs = append(errs, fmt.Errorf("kp.generation=%v != node.generation=%v", kp.ToGeneration, toNode.Generation)) } - if toNode.NumItems == 0 { + switch { + case len(toNode.Items) == 0: errs = append(errs, fmt.Errorf("node.num_items=0")) - } else if kp.ToKey != (btrfsprim.Key{}) && toNode.MinItem != kp.ToKey { + case 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)) + kp.ToKey, toNode.MinItem())) } if len(errs) > 0 { return errs diff --git a/lib/btrfsutil/rebuilt_readitem.go b/lib/btrfsutil/rebuilt_readitem.go index 57440cf..a508d99 100644 --- a/lib/btrfsutil/rebuilt_readitem.go +++ b/lib/btrfsutil/rebuilt_readitem.go @@ -141,8 +141,8 @@ func (o *KeyIO) readNode(ctx context.Context, laddr btrfsvol.LogicalAddr) *diski } return nil }, - MinItem: containers.Optional[btrfsprim.Key]{OK: true, Val: graphInfo.MinItem}, - MaxItem: containers.Optional[btrfsprim.Key]{OK: true, Val: graphInfo.MaxItem}, + 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)) -- cgit v1.2.3-2-g168b From 135adfcd6a0593218daec2657603f61ae49c6130 Mon Sep 17 00:00:00 2001 From: Luke Shumaker Date: Wed, 1 Mar 2023 08:33:26 -0700 Subject: btrfstree: Fix comments --- lib/btrfs/btrfstree/btree_forrest.go | 4 ++-- lib/btrfs/btrfstree/btree_tree.go | 18 +++++++++--------- lib/btrfs/btrfstree/types_node.go | 4 ++-- 3 files changed, 13 insertions(+), 13 deletions(-) (limited to 'lib') diff --git a/lib/btrfs/btrfstree/btree_forrest.go b/lib/btrfs/btrfstree/btree_forrest.go index ace2b49..0bab610 100644 --- a/lib/btrfs/btrfstree/btree_forrest.go +++ b/lib/btrfs/btrfstree/btree_forrest.go @@ -34,8 +34,8 @@ func RootItemSearchFn(treeID btrfsprim.ObjID) func(btrfsprim.Key, uint32) int { } } -// LookupTreeRoot is a utility function to help with implementing the 'Trees' -// interface. +// LookupTreeRoot is a utility function to help with implementing the +// 'TreeOperator' interface. func LookupTreeRoot(fs TreeOperator, sb Superblock, treeID btrfsprim.ObjID) (*TreeRoot, error) { switch treeID { case btrfsprim.ROOT_TREE_OBJECTID: diff --git a/lib/btrfs/btrfstree/btree_tree.go b/lib/btrfs/btrfstree/btree_tree.go index b01312f..a39a795 100644 --- a/lib/btrfs/btrfstree/btree_tree.go +++ b/lib/btrfs/btrfstree/btree_tree.go @@ -37,7 +37,7 @@ type TreeOperator interface { // 002 (read node) // 003 .Node() (or .BadNode()) // for item in node.items: - // if btrfsprim: + // if internal: // 004 .PreKeyPointer() // 005 (recurse) // 006 .PostKeyPointer() @@ -68,7 +68,7 @@ type TreeWalkHandler struct { Node func(TreePath, *diskio.Ref[btrfsvol.LogicalAddr, Node]) error BadNode func(TreePath, *diskio.Ref[btrfsvol.LogicalAddr, Node], error) error PostNode func(TreePath, *diskio.Ref[btrfsvol.LogicalAddr, Node]) error - // Callbacks for items on btrfsprim nodes + // Callbacks for items on internal nodes PreKeyPointer func(TreePath, KeyPointer) error PostKeyPointer func(TreePath, KeyPointer) error // Callbacks for items on leaf nodes @@ -96,7 +96,7 @@ type TreeOperatorImpl struct { NodeSource } -// TreeWalk implements the 'Trees' interface. +// TreeWalk implements the 'TreeOperator' interface. func (fs TreeOperatorImpl) TreeWalk(ctx context.Context, treeID btrfsprim.ObjID, errHandle func(*TreeError), cbs TreeWalkHandler) { sb, err := fs.Superblock() if err != nil { @@ -110,8 +110,8 @@ func (fs TreeOperatorImpl) TreeWalk(ctx context.Context, treeID btrfsprim.ObjID, fs.RawTreeWalk(ctx, *rootInfo, errHandle, cbs) } -// TreeWalk is a utility method to help with implementing the 'Trees'. -// interface. +// RawTreeWalk is a utility method to help with implementing the +// 'TreeOperator' interface. func (fs TreeOperatorImpl) RawTreeWalk(ctx context.Context, rootInfo TreeRoot, errHandle func(*TreeError), cbs TreeWalkHandler) { path := TreePath{{ FromTree: rootInfo.TreeID, @@ -261,7 +261,7 @@ func (fs TreeOperatorImpl) treeSearch(treeRoot TreeRoot, fn func(btrfsprim.Key, } if node.Data.Head.Level > 0 { - // btrfsprim node + // internal node // Search for the right-most node.Data.BodyInternal item for which // `fn(item.Key) >= 0`. @@ -476,7 +476,7 @@ func (fs TreeOperatorImpl) next(path TreePath, node *diskio.Ref[btrfsvol.Logical return path, node, nil } -// TreeSearch implements the 'Trees' interface. +// TreeSearch implements the 'TreeOperator' interface. func (fs TreeOperatorImpl) TreeSearch(treeID btrfsprim.ObjID, fn func(btrfsprim.Key, uint32) int) (Item, error) { sb, err := fs.Superblock() if err != nil { @@ -503,7 +503,7 @@ func KeySearch(fn func(btrfsprim.Key) int) func(btrfsprim.Key, uint32) int { } } -// TreeLookup implements the 'Trees' interface. +// TreeLookup implements the 'TreeOperator' interface. func (fs TreeOperatorImpl) TreeLookup(treeID btrfsprim.ObjID, key btrfsprim.Key) (Item, error) { item, err := fs.TreeSearch(treeID, KeySearch(key.Compare)) if err != nil { @@ -512,7 +512,7 @@ func (fs TreeOperatorImpl) TreeLookup(treeID btrfsprim.ObjID, key btrfsprim.Key) return item, err } -// TreeSearchAll implements the 'Trees' interface. +// TreeSearchAll implements the 'TreeOperator' interface. func (fs TreeOperatorImpl) TreeSearchAll(treeID btrfsprim.ObjID, fn func(btrfsprim.Key, uint32) int) ([]Item, error) { sb, err := fs.Superblock() if err != nil { diff --git a/lib/btrfs/btrfstree/types_node.go b/lib/btrfs/btrfstree/types_node.go index 0a89e05..675cf66 100644 --- a/lib/btrfs/btrfstree/types_node.go +++ b/lib/btrfs/btrfstree/types_node.go @@ -89,7 +89,7 @@ type Node struct { // The node's body (which one of these is present depends on // the node's type, as specified in the header) - BodyInternal []KeyPointer // for btrfsprim nodes + BodyInternal []KeyPointer // for internal nodes BodyLeaf []Item // for leave nodes Padding []byte @@ -105,7 +105,7 @@ type NodeHeader struct { Generation btrfsprim.Generation `bin:"off=0x50, siz=0x8"` Owner btrfsprim.ObjID `bin:"off=0x58, siz=0x8"` // The ID of the tree that contains this node NumItems uint32 `bin:"off=0x60, siz=0x4"` // [ignored-when-writing] - Level uint8 `bin:"off=0x64, siz=0x1"` // 0 for leaf nodes, >=1 for btrfsprim nodes + Level uint8 `bin:"off=0x64, siz=0x1"` // 0 for leaf nodes, >=1 for internal nodes binstruct.End `bin:"off=0x65"` } -- cgit v1.2.3-2-g168b From 7349ff1a01b29eae7f7e769fe44548f09c253d2b Mon Sep 17 00:00:00 2001 From: Luke Shumaker Date: Thu, 2 Mar 2023 17:25:49 -0700 Subject: tree-wide: Have "interior" rather than "internal" be the antonym of "leaf" Because "internal" has a meaning in the Go world, and it's confusing. --- lib/btrfs/btrfstree/btree_tree.go | 52 +++++++++++++++++++-------------------- lib/btrfs/btrfstree/types_node.go | 32 ++++++++++++------------ lib/btrfsutil/graph.go | 4 +-- lib/btrfsutil/skinny_paths.go | 8 +++--- 4 files changed, 48 insertions(+), 48 deletions(-) (limited to 'lib') diff --git a/lib/btrfs/btrfstree/btree_tree.go b/lib/btrfs/btrfstree/btree_tree.go index a39a795..f88dd44 100644 --- a/lib/btrfs/btrfstree/btree_tree.go +++ b/lib/btrfs/btrfstree/btree_tree.go @@ -37,7 +37,7 @@ type TreeOperator interface { // 002 (read node) // 003 .Node() (or .BadNode()) // for item in node.items: - // if internal: + // if interior: // 004 .PreKeyPointer() // 005 (recurse) // 006 .PostKeyPointer() @@ -68,7 +68,7 @@ type TreeWalkHandler struct { Node func(TreePath, *diskio.Ref[btrfsvol.LogicalAddr, Node]) error BadNode func(TreePath, *diskio.Ref[btrfsvol.LogicalAddr, Node], error) error PostNode func(TreePath, *diskio.Ref[btrfsvol.LogicalAddr, Node]) error - // Callbacks for items on internal nodes + // Callbacks for items on interior nodes PreKeyPointer func(TreePath, KeyPointer) error PostKeyPointer func(TreePath, KeyPointer) error // Callbacks for items on leaf nodes @@ -169,10 +169,10 @@ func (fs TreeOperatorImpl) treeWalk(ctx context.Context, path TreePath, errHandl return } if node != nil { - for i, item := range node.Data.BodyInternal { + for i, item := range node.Data.BodyInterior { toMaxKey := path.Node(-1).ToMaxKey - if i+1 < len(node.Data.BodyInternal) { - toMaxKey = node.Data.BodyInternal[i+1].Key.Mm() + if i+1 < len(node.Data.BodyInterior) { + toMaxKey = node.Data.BodyInterior[i+1].Key.Mm() } itemPath := append(path, TreePathElem{ FromTree: node.Data.Head.Owner, @@ -261,9 +261,9 @@ func (fs TreeOperatorImpl) treeSearch(treeRoot TreeRoot, fn func(btrfsprim.Key, } if node.Data.Head.Level > 0 { - // internal node + // interior node - // Search for the right-most node.Data.BodyInternal item for which + // Search for the right-most node.Data.BodyInterior item for which // `fn(item.Key) >= 0`. // // + + + + 0 - - - - @@ -271,7 +271,7 @@ func (fs TreeOperatorImpl) treeSearch(treeRoot TreeRoot, fn func(btrfsprim.Key, // There may or may not be a value that returns '0'. // // i.e. find the highest value that isn't too high. - lastGood, ok := slices.SearchHighest(node.Data.BodyInternal, func(kp KeyPointer) int { + lastGood, ok := slices.SearchHighest(node.Data.BodyInterior, func(kp KeyPointer) int { return slices.Min(fn(kp.Key, math.MaxUint32), 0) // don't return >0; a key can't be "too low" }) if !ok { @@ -279,16 +279,16 @@ func (fs TreeOperatorImpl) treeSearch(treeRoot TreeRoot, fn func(btrfsprim.Key, return nil, nil, iofs.ErrNotExist } toMaxKey := path.Node(-1).ToMaxKey - if lastGood+1 < len(node.Data.BodyInternal) { - toMaxKey = node.Data.BodyInternal[lastGood+1].Key.Mm() + if lastGood+1 < len(node.Data.BodyInterior) { + toMaxKey = node.Data.BodyInterior[lastGood+1].Key.Mm() } path = append(path, TreePathElem{ FromTree: node.Data.Head.Owner, FromItemIdx: lastGood, - ToNodeAddr: node.Data.BodyInternal[lastGood].BlockPtr, - ToNodeGeneration: node.Data.BodyInternal[lastGood].Generation, + ToNodeAddr: node.Data.BodyInterior[lastGood].BlockPtr, + ToNodeGeneration: node.Data.BodyInterior[lastGood].Generation, ToNodeLevel: node.Data.Head.Level - 1, - ToKey: node.Data.BodyInternal[lastGood].Key, + ToKey: node.Data.BodyInterior[lastGood].Key, ToMaxKey: toMaxKey, }) FreeNodeRef(node) @@ -344,7 +344,7 @@ func (fs TreeOperatorImpl) prev(path TreePath, node *diskio.Ref[btrfsvol.Logical FreeNodeRef(node) return nil, nil, err } - path.Node(-1).ToNodeAddr = node.Data.BodyInternal[path.Node(-1).FromItemIdx].BlockPtr + path.Node(-1).ToNodeAddr = node.Data.BodyInterior[path.Node(-1).FromItemIdx].BlockPtr } } // go down @@ -360,11 +360,11 @@ func (fs TreeOperatorImpl) prev(path TreePath, node *diskio.Ref[btrfsvol.Logical if node.Data.Head.Level > 0 { path = append(path, TreePathElem{ FromTree: node.Data.Head.Owner, - FromItemIdx: len(node.Data.BodyInternal) - 1, - ToNodeAddr: node.Data.BodyInternal[len(node.Data.BodyInternal)-1].BlockPtr, - ToNodeGeneration: node.Data.BodyInternal[len(node.Data.BodyInternal)-1].Generation, + FromItemIdx: len(node.Data.BodyInterior) - 1, + ToNodeAddr: node.Data.BodyInterior[len(node.Data.BodyInterior)-1].BlockPtr, + ToNodeGeneration: node.Data.BodyInterior[len(node.Data.BodyInterior)-1].Generation, ToNodeLevel: node.Data.Head.Level - 1, - ToKey: node.Data.BodyInternal[len(node.Data.BodyInternal)-1].Key, + ToKey: node.Data.BodyInterior[len(node.Data.BodyInterior)-1].Key, ToMaxKey: path.Node(-1).ToMaxKey, }) } else { @@ -427,7 +427,7 @@ func (fs TreeOperatorImpl) next(path TreePath, node *diskio.Ref[btrfsvol.Logical FreeNodeRef(node) return nil, nil, err } - path.Node(-1).ToNodeAddr = node.Data.BodyInternal[path.Node(-1).FromItemIdx].BlockPtr + path.Node(-1).ToNodeAddr = node.Data.BodyInterior[path.Node(-1).FromItemIdx].BlockPtr } } // go down @@ -443,24 +443,24 @@ func (fs TreeOperatorImpl) next(path TreePath, node *diskio.Ref[btrfsvol.Logical } if node.Data.Head.Level > 0 { toMaxKey := path.Node(-1).ToMaxKey - if len(node.Data.BodyInternal) > 1 { - toMaxKey = node.Data.BodyInternal[1].Key.Mm() + if len(node.Data.BodyInterior) > 1 { + toMaxKey = node.Data.BodyInterior[1].Key.Mm() } path = append(path, TreePathElem{ FromTree: node.Data.Head.Owner, FromItemIdx: 0, - ToNodeAddr: node.Data.BodyInternal[0].BlockPtr, - ToNodeGeneration: node.Data.BodyInternal[0].Generation, + ToNodeAddr: node.Data.BodyInterior[0].BlockPtr, + ToNodeGeneration: node.Data.BodyInterior[0].Generation, ToNodeLevel: node.Data.Head.Level - 1, - ToKey: node.Data.BodyInternal[0].Key, + ToKey: node.Data.BodyInterior[0].Key, ToMaxKey: toMaxKey, }) } else { path = append(path, TreePathElem{ FromTree: node.Data.Head.Owner, FromItemIdx: 0, - ToKey: node.Data.BodyInternal[0].Key, - ToMaxKey: node.Data.BodyInternal[0].Key, + ToKey: node.Data.BodyInterior[0].Key, + ToMaxKey: node.Data.BodyInterior[0].Key, }) } } diff --git a/lib/btrfs/btrfstree/types_node.go b/lib/btrfs/btrfstree/types_node.go index 675cf66..150539d 100644 --- a/lib/btrfs/btrfstree/types_node.go +++ b/lib/btrfs/btrfstree/types_node.go @@ -89,7 +89,7 @@ type Node struct { // The node's body (which one of these is present depends on // the node's type, as specified in the header) - BodyInternal []KeyPointer // for internal nodes + BodyInterior []KeyPointer // for interior nodes BodyLeaf []Item // for leave nodes Padding []byte @@ -105,7 +105,7 @@ type NodeHeader struct { Generation btrfsprim.Generation `bin:"off=0x50, siz=0x8"` Owner btrfsprim.ObjID `bin:"off=0x58, siz=0x8"` // The ID of the tree that contains this node NumItems uint32 `bin:"off=0x60, siz=0x4"` // [ignored-when-writing] - Level uint8 `bin:"off=0x64, siz=0x1"` // 0 for leaf nodes, >=1 for internal nodes + Level uint8 `bin:"off=0x64, siz=0x1"` // 0 for leaf nodes, >=1 for interior nodes binstruct.End `bin:"off=0x65"` } @@ -122,10 +122,10 @@ func (node Node) MaxItems() uint32 { func (node Node) MinItem() (btrfsprim.Key, bool) { if node.Head.Level > 0 { - if len(node.BodyInternal) == 0 { + if len(node.BodyInterior) == 0 { return btrfsprim.Key{}, false } - return node.BodyInternal[0].Key, true + return node.BodyInterior[0].Key, true } else { if len(node.BodyLeaf) == 0 { return btrfsprim.Key{}, false @@ -136,10 +136,10 @@ func (node Node) MinItem() (btrfsprim.Key, bool) { func (node Node) MaxItem() (btrfsprim.Key, bool) { if node.Head.Level > 0 { - if len(node.BodyInternal) == 0 { + if len(node.BodyInterior) == 0 { return btrfsprim.Key{}, false } - return node.BodyInternal[len(node.BodyInternal)-1].Key, true + return node.BodyInterior[len(node.BodyInterior)-1].Key, true } else { if len(node.BodyLeaf) == 0 { return btrfsprim.Key{}, false @@ -186,7 +186,7 @@ func (node *Node) UnmarshalBinary(nodeBuf []byte) (int, error) { n, nodeHeaderSize) } if node.Head.Level > 0 { - _n, err := node.unmarshalInternal(nodeBuf[n:]) + _n, err := node.unmarshalInterior(nodeBuf[n:]) n += _n if err != nil { return n, fmt.Errorf("btrfsprim: %w", err) @@ -214,7 +214,7 @@ func (node Node) MarshalBinary() ([]byte, error) { nodeHeaderSize, node.Size) } if node.Head.Level > 0 { - node.Head.NumItems = uint32(len(node.BodyInternal)) + node.Head.NumItems = uint32(len(node.BodyInterior)) } else { node.Head.NumItems = uint32(len(node.BodyLeaf)) } @@ -232,7 +232,7 @@ func (node Node) MarshalBinary() ([]byte, error) { } if node.Head.Level > 0 { - if err := node.marshalInternalTo(buf[nodeHeaderSize:]); err != nil { + if err := node.marshalInteriorTo(buf[nodeHeaderSize:]); err != nil { return buf, err } } else { @@ -244,7 +244,7 @@ func (node Node) MarshalBinary() ([]byte, error) { return buf, nil } -// Node: "internal" //////////////////////////////////////////////////////////////////////////////// +// Node: "interior" //////////////////////////////////////////////////////////////////////////////// type KeyPointer struct { Key btrfsprim.Key `bin:"off=0x0, siz=0x11"` @@ -253,11 +253,11 @@ type KeyPointer struct { binstruct.End `bin:"off=0x21"` } -func (node *Node) unmarshalInternal(bodyBuf []byte) (int, error) { +func (node *Node) unmarshalInterior(bodyBuf []byte) (int, error) { n := 0 - node.BodyInternal = make([]KeyPointer, node.Head.NumItems) - for i := range node.BodyInternal { - _n, err := binstruct.Unmarshal(bodyBuf[n:], &node.BodyInternal[i]) + node.BodyInterior = make([]KeyPointer, node.Head.NumItems) + for i := range node.BodyInterior { + _n, err := binstruct.Unmarshal(bodyBuf[n:], &node.BodyInterior[i]) n += _n if err != nil { return n, fmt.Errorf("item %v: %w", i, err) @@ -267,9 +267,9 @@ func (node *Node) unmarshalInternal(bodyBuf []byte) (int, error) { return len(bodyBuf), nil } -func (node *Node) marshalInternalTo(bodyBuf []byte) error { +func (node *Node) marshalInteriorTo(bodyBuf []byte) error { n := 0 - for i, item := range node.BodyInternal { + for i, item := range node.BodyInterior { bs, err := binstruct.Marshal(item) if err != nil { return fmt.Errorf("item %v: %w", i, err) diff --git a/lib/btrfsutil/graph.go b/lib/btrfsutil/graph.go index 9e453eb..09a17b4 100644 --- a/lib/btrfsutil/graph.go +++ b/lib/btrfsutil/graph.go @@ -183,8 +183,8 @@ func (g Graph) InsertNode(nodeRef *diskio.Ref[btrfsvol.LogicalAddr, btrfstree.No } } else { g.Nodes[nodeRef.Addr] = nodeData - kps := make([]GraphEdge, len(nodeRef.Data.BodyInternal)) - for i, kp := range nodeRef.Data.BodyInternal { + kps := make([]GraphEdge, len(nodeRef.Data.BodyInterior)) + for i, kp := range nodeRef.Data.BodyInterior { kps[i] = GraphEdge{ FromNode: nodeRef.Addr, FromItem: i, diff --git a/lib/btrfsutil/skinny_paths.go b/lib/btrfsutil/skinny_paths.go index 1695990..da86273 100644 --- a/lib/btrfsutil/skinny_paths.go +++ b/lib/btrfsutil/skinny_paths.go @@ -60,13 +60,13 @@ func (a *SkinnyPathArena) getItem(parent btrfstree.TreePath, itemIdx int) (btrfs return btrfstree.TreePathElem{}, err } if node.Data.Head.Level > 0 { - if itemIdx >= len(node.Data.BodyInternal) { + if itemIdx >= len(node.Data.BodyInterior) { panic("should not happen") } - for i, item := range node.Data.BodyInternal { + for i, item := range node.Data.BodyInterior { toMaxKey := parent.Node(-1).ToMaxKey - if i+1 < len(node.Data.BodyInternal) { - toMaxKey = node.Data.BodyInternal[i+1].Key.Mm() + if i+1 < len(node.Data.BodyInterior) { + toMaxKey = node.Data.BodyInterior[i+1].Key.Mm() } elem := btrfstree.TreePathElem{ FromTree: node.Data.Head.Owner, -- cgit v1.2.3-2-g168b From 2c2d616b8650dd01818bd29e11e7b06ae2de5891 Mon Sep 17 00:00:00 2001 From: Luke Shumaker Date: Sat, 4 Mar 2023 09:51:34 -0700 Subject: tree-wide: Refer to item "slots" rather than "indexes" --- lib/btrfs/btrfstree/btree_tree.go | 66 ++++++++++++++++++------------------ lib/btrfs/btrfstree/path.go | 22 ++++++------ lib/btrfsutil/old_rebuilt_forrest.go | 6 ++-- lib/btrfsutil/rebuilt_readitem.go | 18 +++++----- lib/btrfsutil/rebuilt_tree.go | 2 +- lib/btrfsutil/skinny_paths.go | 32 ++++++++--------- 6 files changed, 73 insertions(+), 73 deletions(-) (limited to 'lib') diff --git a/lib/btrfs/btrfstree/btree_tree.go b/lib/btrfs/btrfstree/btree_tree.go index f88dd44..e75eb0b 100644 --- a/lib/btrfs/btrfstree/btree_tree.go +++ b/lib/btrfs/btrfstree/btree_tree.go @@ -115,7 +115,7 @@ func (fs TreeOperatorImpl) TreeWalk(ctx context.Context, treeID btrfsprim.ObjID, func (fs TreeOperatorImpl) RawTreeWalk(ctx context.Context, rootInfo TreeRoot, errHandle func(*TreeError), cbs TreeWalkHandler) { path := TreePath{{ FromTree: rootInfo.TreeID, - FromItemIdx: -1, + FromItemSlot: -1, ToNodeAddr: rootInfo.RootNode, ToNodeGeneration: rootInfo.Generation, ToNodeLevel: rootInfo.Level, @@ -176,7 +176,7 @@ func (fs TreeOperatorImpl) treeWalk(ctx context.Context, path TreePath, errHandl } itemPath := append(path, TreePathElem{ FromTree: node.Data.Head.Owner, - FromItemIdx: i, + FromItemSlot: i, ToNodeAddr: item.BlockPtr, ToNodeGeneration: item.Generation, ToNodeLevel: node.Data.Head.Level - 1, @@ -203,10 +203,10 @@ func (fs TreeOperatorImpl) treeWalk(ctx context.Context, path TreePath, errHandl } for i, item := range node.Data.BodyLeaf { itemPath := append(path, TreePathElem{ - FromTree: node.Data.Head.Owner, - FromItemIdx: i, - ToKey: item.Key, - ToMaxKey: item.Key, + FromTree: node.Data.Head.Owner, + FromItemSlot: i, + ToKey: item.Key, + ToMaxKey: item.Key, }) if errBody, isErr := item.Body.(*btrfsitem.Error); isErr { if cbs.BadItem == nil { @@ -244,7 +244,7 @@ func (fs TreeOperatorImpl) treeWalk(ctx context.Context, path TreePath, errHandl func (fs TreeOperatorImpl) treeSearch(treeRoot TreeRoot, fn func(btrfsprim.Key, uint32) int) (TreePath, *diskio.Ref[btrfsvol.LogicalAddr, Node], error) { path := TreePath{{ FromTree: treeRoot.TreeID, - FromItemIdx: -1, + FromItemSlot: -1, ToNodeAddr: treeRoot.RootNode, ToNodeGeneration: treeRoot.Generation, ToNodeLevel: treeRoot.Level, @@ -284,7 +284,7 @@ func (fs TreeOperatorImpl) treeSearch(treeRoot TreeRoot, fn func(btrfsprim.Key, } path = append(path, TreePathElem{ FromTree: node.Data.Head.Owner, - FromItemIdx: lastGood, + FromItemSlot: lastGood, ToNodeAddr: node.Data.BodyInterior[lastGood].BlockPtr, ToNodeGeneration: node.Data.BodyInterior[lastGood].Generation, ToNodeLevel: node.Data.Head.Level - 1, @@ -305,7 +305,7 @@ func (fs TreeOperatorImpl) treeSearch(treeRoot TreeRoot, fn func(btrfsprim.Key, // is returned. // // Implement this search as a binary search. - idx, ok := slices.Search(node.Data.BodyLeaf, func(item Item) int { + slot, ok := slices.Search(node.Data.BodyLeaf, func(item Item) int { return fn(item.Key, item.BodySize) }) if !ok { @@ -313,10 +313,10 @@ func (fs TreeOperatorImpl) treeSearch(treeRoot TreeRoot, fn func(btrfsprim.Key, return nil, nil, iofs.ErrNotExist } path = append(path, TreePathElem{ - FromTree: node.Data.Head.Owner, - FromItemIdx: idx, - ToKey: node.Data.BodyLeaf[idx].Key, - ToMaxKey: node.Data.BodyLeaf[idx].Key, + FromTree: node.Data.Head.Owner, + FromItemSlot: slot, + ToKey: node.Data.BodyLeaf[slot].Key, + ToMaxKey: node.Data.BodyLeaf[slot].Key, }) return path, node, nil } @@ -328,14 +328,14 @@ func (fs TreeOperatorImpl) prev(path TreePath, node *diskio.Ref[btrfsvol.Logical path = path.DeepCopy() // go up - for path.Node(-1).FromItemIdx < 1 { + for path.Node(-1).FromItemSlot < 1 { path = path.Parent() if len(path) == 0 { return nil, nil, nil } } // go left - path.Node(-1).FromItemIdx-- + path.Node(-1).FromItemSlot-- if path.Node(-1).ToNodeAddr != 0 { if node.Addr != path.Node(-2).ToNodeAddr { FreeNodeRef(node) @@ -344,7 +344,7 @@ func (fs TreeOperatorImpl) prev(path TreePath, node *diskio.Ref[btrfsvol.Logical FreeNodeRef(node) return nil, nil, err } - path.Node(-1).ToNodeAddr = node.Data.BodyInterior[path.Node(-1).FromItemIdx].BlockPtr + path.Node(-1).ToNodeAddr = node.Data.BodyInterior[path.Node(-1).FromItemSlot].BlockPtr } } // go down @@ -360,7 +360,7 @@ func (fs TreeOperatorImpl) prev(path TreePath, node *diskio.Ref[btrfsvol.Logical if node.Data.Head.Level > 0 { path = append(path, TreePathElem{ FromTree: node.Data.Head.Owner, - FromItemIdx: len(node.Data.BodyInterior) - 1, + FromItemSlot: len(node.Data.BodyInterior) - 1, ToNodeAddr: node.Data.BodyInterior[len(node.Data.BodyInterior)-1].BlockPtr, ToNodeGeneration: node.Data.BodyInterior[len(node.Data.BodyInterior)-1].Generation, ToNodeLevel: node.Data.Head.Level - 1, @@ -369,10 +369,10 @@ func (fs TreeOperatorImpl) prev(path TreePath, node *diskio.Ref[btrfsvol.Logical }) } else { path = append(path, TreePathElem{ - FromTree: node.Data.Head.Owner, - FromItemIdx: len(node.Data.BodyLeaf) - 1, - ToKey: node.Data.BodyLeaf[len(node.Data.BodyLeaf)-1].Key, - ToMaxKey: node.Data.BodyLeaf[len(node.Data.BodyLeaf)-1].Key, + FromTree: node.Data.Head.Owner, + FromItemSlot: len(node.Data.BodyLeaf) - 1, + ToKey: node.Data.BodyLeaf[len(node.Data.BodyLeaf)-1].Key, + ToMaxKey: node.Data.BodyLeaf[len(node.Data.BodyLeaf)-1].Key, }) } } @@ -402,7 +402,7 @@ func (fs TreeOperatorImpl) next(path TreePath, node *diskio.Ref[btrfsvol.Logical } path.Node(-2).ToNodeLevel = node.Data.Head.Level } - for path.Node(-1).FromItemIdx+1 >= int(node.Data.Head.NumItems) { + for path.Node(-1).FromItemSlot+1 >= int(node.Data.Head.NumItems) { path = path.Parent() if len(path) == 1 { return nil, nil, nil @@ -418,7 +418,7 @@ func (fs TreeOperatorImpl) next(path TreePath, node *diskio.Ref[btrfsvol.Logical } } // go right - path.Node(-1).FromItemIdx++ + path.Node(-1).FromItemSlot++ if path.Node(-1).ToNodeAddr != 0 { if node.Addr != path.Node(-2).ToNodeAddr { FreeNodeRef(node) @@ -427,7 +427,7 @@ func (fs TreeOperatorImpl) next(path TreePath, node *diskio.Ref[btrfsvol.Logical FreeNodeRef(node) return nil, nil, err } - path.Node(-1).ToNodeAddr = node.Data.BodyInterior[path.Node(-1).FromItemIdx].BlockPtr + path.Node(-1).ToNodeAddr = node.Data.BodyInterior[path.Node(-1).FromItemSlot].BlockPtr } } // go down @@ -448,7 +448,7 @@ func (fs TreeOperatorImpl) next(path TreePath, node *diskio.Ref[btrfsvol.Logical } path = append(path, TreePathElem{ FromTree: node.Data.Head.Owner, - FromItemIdx: 0, + FromItemSlot: 0, ToNodeAddr: node.Data.BodyInterior[0].BlockPtr, ToNodeGeneration: node.Data.BodyInterior[0].Generation, ToNodeLevel: node.Data.Head.Level - 1, @@ -457,10 +457,10 @@ func (fs TreeOperatorImpl) next(path TreePath, node *diskio.Ref[btrfsvol.Logical }) } else { path = append(path, TreePathElem{ - FromTree: node.Data.Head.Owner, - FromItemIdx: 0, - ToKey: node.Data.BodyInterior[0].Key, - ToMaxKey: node.Data.BodyInterior[0].Key, + FromTree: node.Data.Head.Owner, + FromItemSlot: 0, + ToKey: node.Data.BodyInterior[0].Key, + ToMaxKey: node.Data.BodyInterior[0].Key, }) } } @@ -490,7 +490,7 @@ func (fs TreeOperatorImpl) TreeSearch(treeID btrfsprim.ObjID, fn func(btrfsprim. if err != nil { return Item{}, err } - item := node.Data.BodyLeaf[path.Node(-1).FromItemIdx] + item := node.Data.BodyLeaf[path.Node(-1).FromItemSlot] item.Body = item.Body.CloneItem() FreeNodeRef(node) return item, nil @@ -526,7 +526,7 @@ func (fs TreeOperatorImpl) TreeSearchAll(treeID btrfsprim.ObjID, fn func(btrfspr if err != nil { return nil, err } - middleItem := middleNode.Data.BodyLeaf[middlePath.Node(-1).FromItemIdx] + middleItem := middleNode.Data.BodyLeaf[middlePath.Node(-1).FromItemSlot] ret := []Item{middleItem} var errs derror.MultiError @@ -540,7 +540,7 @@ func (fs TreeOperatorImpl) TreeSearchAll(treeID btrfsprim.ObjID, fn func(btrfspr if len(prevPath) == 0 { break } - prevItem := prevNode.Data.BodyLeaf[prevPath.Node(-1).FromItemIdx] + prevItem := prevNode.Data.BodyLeaf[prevPath.Node(-1).FromItemSlot] if fn(prevItem.Key, prevItem.BodySize) != 0 { break } @@ -567,7 +567,7 @@ func (fs TreeOperatorImpl) TreeSearchAll(treeID btrfsprim.ObjID, fn func(btrfspr if len(nextPath) == 0 { break } - nextItem := nextNode.Data.BodyLeaf[nextPath.Node(-1).FromItemIdx] + nextItem := nextNode.Data.BodyLeaf[nextPath.Node(-1).FromItemSlot] if fn(nextItem.Key, nextItem.BodySize) != 0 { break } diff --git a/lib/btrfs/btrfstree/path.go b/lib/btrfs/btrfstree/path.go index dd2cb74..9b1a5c7 100644 --- a/lib/btrfs/btrfstree/path.go +++ b/lib/btrfs/btrfstree/path.go @@ -1,4 +1,4 @@ -// Copyright (C) 2022 Luke Shumaker +// Copyright (C) 2022-2023 Luke Shumaker // // SPDX-License-Identifier: GPL-2.0-or-later @@ -17,7 +17,7 @@ import ( // system) to the a node or item within one of the btrees in the // system. // -// - The first element will always have an ItemIdx of -1. +// - The first element will always have an ItemSlot of -1. // // - For .Item() callbacks, the last element will always have a // NodeAddr of 0. @@ -26,7 +26,7 @@ import ( // // [superblock: tree=B, lvl=3, gen=6] // | -// | <------------------------------------------ pathElem={from_tree:B, from_idx=-1, +// | <------------------------------------------ pathElem={from_tree:B, from_slot=-1, // | to_addr:0x01, to_gen=6, to_lvl=3} // +[0x01]-------------+ // | lvl=3 gen=6 own=B | @@ -34,7 +34,7 @@ import ( // |0|1|2|3|4|5|6|7|8|9| // +-+-+-+-+-+-+-+-+-+-+ // | -// | <------------------------------ pathElem:{from_tree:B, from_idx:7, +// | <------------------------------ pathElem:{from_tree:B, from_slot:7, // | to_addr:0x02, to_gen:5, to_lvl:2} // +[0x02]--------------+ // | lvl=2 gen=5 own=B | @@ -42,7 +42,7 @@ import ( // |0|1|2|3|4|5|6|7|8|9| // +-+-+-+-+-+-+-+-+-+-+ // | -// | <-------------------- pathElem={from_tree:B, from_idx:6, +// | <-------------------- pathElem={from_tree:B, from_slot:6, // | to_addr:0x03, to_gen:5, to_lvl:1} // +[0x03]-------------+ // | lvl=1 gen=5 own=A | @@ -50,7 +50,7 @@ import ( // |0|1|2|3|4|5|6|7|8|9| // +-+-+-+-+-+-+-+-+-+-+ // | -// | <---------------- pathElem={from_tree:A, from_idx:3, +// | <---------------- pathElem={from_tree:A, from_slot:3, // | to_addr:0x04, to_gen:2, lvl:0} // +[0x04]-------------+ // | lvl=0 gen=2 own=A | @@ -58,7 +58,7 @@ import ( // |0|1|2|3|4|5|6|7|8|9| // +-+-+-+-+-+-+-+-+-+-+ // | -// | <--------------- pathElem={from_tree:A, from_idx:1, +// | <--------------- pathElem={from_tree:A, from_slot:1, // | to_addr:0, to_gen: 0, to_lvl:0} // [item] type TreePath []TreePathElem @@ -68,9 +68,9 @@ type TreePathElem struct { // FromTree is the owning tree ID of the parent node; or the // well-known tree ID if this is the root. FromTree btrfsprim.ObjID - // FromItemIdx is the index of this KeyPointer in the parent + // FromItemSlot is the index of this KeyPointer in the parent // Node; or -1 if this is the root and there is no KeyPointer. - FromItemIdx int + FromItemSlot int // ToNodeAddr is the address of the node that the KeyPointer // points at, or 0 if this is a leaf item and nothing is being @@ -104,13 +104,13 @@ func (path TreePath) String() string { } else { var ret strings.Builder fmt.Fprintf(&ret, "%s->", path[0].FromTree.Format(btrfsprim.ROOT_TREE_OBJECTID)) - if len(path) == 1 && path[0] == (TreePathElem{FromTree: path[0].FromTree, FromItemIdx: -1}) { + if len(path) == 1 && path[0] == (TreePathElem{FromTree: path[0].FromTree, FromItemSlot: -1}) { ret.WriteString("(empty-path)") } else { path[0].writeNodeTo(&ret) } for _, elem := range path[1:] { - fmt.Fprintf(&ret, "[%v]", elem.FromItemIdx) + fmt.Fprintf(&ret, "[%v]", elem.FromItemSlot) if elem.ToNodeAddr != 0 { ret.WriteString("->") elem.writeNodeTo(&ret) diff --git a/lib/btrfsutil/old_rebuilt_forrest.go b/lib/btrfsutil/old_rebuilt_forrest.go index 2386803..6014793 100644 --- a/lib/btrfsutil/old_rebuilt_forrest.go +++ b/lib/btrfsutil/old_rebuilt_forrest.go @@ -237,7 +237,7 @@ func (bt *OldRebuiltForrest) TreeSearch(treeID btrfsprim.ObjID, fn func(btrfspri return btrfstree.Item{}, bt.addErrs(tree, fn, err) } - item := node.Data.BodyLeaf[itemPath.Node(-1).FromItemIdx] + item := node.Data.BodyLeaf[itemPath.Node(-1).FromItemSlot] item.Body = item.Body.CloneItem() // Since we were only asked to return 1 item, it isn't @@ -275,7 +275,7 @@ func (bt *OldRebuiltForrest) TreeSearchAll(treeID btrfsprim.ObjID, fn func(btrfs return nil, bt.addErrs(tree, fn, err) } } - ret[i] = node.Data.BodyLeaf[itemPath.Node(-1).FromItemIdx] + ret[i] = node.Data.BodyLeaf[itemPath.Node(-1).FromItemSlot] ret[i].Body = ret[i].Body.CloneItem() } btrfstree.FreeNodeRef(node) @@ -315,7 +315,7 @@ func (bt *OldRebuiltForrest) TreeWalk(ctx context.Context, treeID btrfsprim.ObjI return true } } - item := node.Data.BodyLeaf[itemPath.Node(-1).FromItemIdx] + item := node.Data.BodyLeaf[itemPath.Node(-1).FromItemSlot] if err := cbs.Item(itemPath, item); err != nil { errHandle(&btrfstree.TreeError{Path: itemPath, Err: err}) } diff --git a/lib/btrfsutil/rebuilt_readitem.go b/lib/btrfsutil/rebuilt_readitem.go index a508d99..016299c 100644 --- a/lib/btrfsutil/rebuilt_readitem.go +++ b/lib/btrfsutil/rebuilt_readitem.go @@ -22,11 +22,11 @@ import ( type ItemPtr struct { Node btrfsvol.LogicalAddr - Idx int + Slot int } func (ptr ItemPtr) String() string { - return fmt.Sprintf("node@%v[%v]", ptr.Node, ptr.Idx) + return fmt.Sprintf("node@%v[%v]", ptr.Node, ptr.Slot) } type SizeAndErr struct { @@ -74,7 +74,7 @@ func (o *KeyIO) InsertNode(nodeRef *diskio.Ref[btrfsvol.LogicalAddr, btrfstree.N for i, item := range nodeRef.Data.BodyLeaf { ptr := ItemPtr{ Node: nodeRef.Addr, - Idx: i, + Slot: i, } switch itemBody := item.Body.(type) { case *btrfsitem.Inode: @@ -159,13 +159,13 @@ func (o *KeyIO) ReadItem(ctx context.Context, ptr ItemPtr) btrfsitem.Item { 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)) + if ptr.Slot < 0 { + panic(fmt.Errorf("should not happen: btrfsutil.KeyIO.ReadItem called for negative item slot: %v", ptr.Slot)) } 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))) + if ptr.Slot >= len(items) { + panic(fmt.Errorf("should not happen: btrfsutil.KeyIO.ReadItem called for out-of-bounds item slot: slot=%v len=%v", + ptr.Slot, len(items))) } - return items[ptr.Idx].Body.CloneItem() + return items[ptr.Slot].Body.CloneItem() } diff --git a/lib/btrfsutil/rebuilt_tree.go b/lib/btrfsutil/rebuilt_tree.go index 1009204..9e23074 100644 --- a/lib/btrfsutil/rebuilt_tree.go +++ b/lib/btrfsutil/rebuilt_tree.go @@ -192,7 +192,7 @@ func (tree *RebuiltTree) items(ctx context.Context, cache containers.Map[btrfspr for j, itemKey := range tree.forrest.graph.Nodes[leaf].Items { newPtr := ItemPtr{ Node: leaf, - Idx: j, + Slot: j, } if oldPtr, exists := index.Load(itemKey); !exists { index.Store(itemKey, newPtr) diff --git a/lib/btrfsutil/skinny_paths.go b/lib/btrfsutil/skinny_paths.go index da86273..adf539b 100644 --- a/lib/btrfsutil/skinny_paths.go +++ b/lib/btrfsutil/skinny_paths.go @@ -39,8 +39,8 @@ func (a *SkinnyPathArena) init() { } } -func (a *SkinnyPathArena) getItem(parent btrfstree.TreePath, itemIdx int) (btrfstree.TreePathElem, error) { - if itemIdx < 0 { +func (a *SkinnyPathArena) getItem(parent btrfstree.TreePath, itemSlot int) (btrfstree.TreePathElem, error) { + if itemSlot < 0 { panic("should not happen") } @@ -48,7 +48,7 @@ func (a *SkinnyPathArena) getItem(parent btrfstree.TreePath, itemIdx int) (btrfs ret, ok := a.fatItems.Load(skinnyItem{ Node: parent.Node(-1).ToNodeAddr, - Item: itemIdx, + Item: itemSlot, }) if ok { return ret, nil @@ -60,7 +60,7 @@ func (a *SkinnyPathArena) getItem(parent btrfstree.TreePath, itemIdx int) (btrfs return btrfstree.TreePathElem{}, err } if node.Data.Head.Level > 0 { - if itemIdx >= len(node.Data.BodyInterior) { + if itemSlot >= len(node.Data.BodyInterior) { panic("should not happen") } for i, item := range node.Data.BodyInterior { @@ -70,7 +70,7 @@ func (a *SkinnyPathArena) getItem(parent btrfstree.TreePath, itemIdx int) (btrfs } elem := btrfstree.TreePathElem{ FromTree: node.Data.Head.Owner, - FromItemIdx: i, + FromItemSlot: i, ToNodeAddr: item.BlockPtr, ToNodeGeneration: item.Generation, ToNodeLevel: node.Data.Head.Level - 1, @@ -78,23 +78,23 @@ func (a *SkinnyPathArena) getItem(parent btrfstree.TreePath, itemIdx int) (btrfs ToMaxKey: toMaxKey, } a.fatItems.Store(skinnyItem{Node: parent.Node(-1).ToNodeAddr, Item: i}, elem) - if i == itemIdx { + if i == itemSlot { ret = elem } } } else { - if itemIdx >= len(node.Data.BodyLeaf) { + if itemSlot >= 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, + FromTree: node.Data.Head.Owner, + FromItemSlot: i, + ToKey: item.Key, + ToMaxKey: item.Key, } a.fatItems.Store(skinnyItem{Node: parent.Node(-1).ToNodeAddr, Item: i}, elem) - if i == itemIdx { + if i == itemSlot { ret = elem } } @@ -114,8 +114,8 @@ func (a *SkinnyPathArena) Deflate(fat btrfstree.TreePath) SkinnyPath { 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) + a.fatItems.Store(skinnyItem{Node: prevNode, Item: elem.FromItemSlot}, elem) + ret.Items = append(ret.Items, elem.FromItemSlot) } prevNode = elem.ToNodeAddr } @@ -134,8 +134,8 @@ func (a *SkinnyPathArena) Inflate(skinny SkinnyPath) btrfstree.TreePath { } ret = append(ret, root) - for _, itemIdx := range skinny.Items { - elem, err := a.getItem(ret, itemIdx) + for _, itemSlot := range skinny.Items { + elem, err := a.getItem(ret, itemSlot) if err != nil { panic(err) } -- cgit v1.2.3-2-g168b From a2a92e721fcae47d196c5cd45f78f0e69b48278b Mon Sep 17 00:00:00 2001 From: Luke Shumaker Date: Mon, 13 Mar 2023 15:04:39 -0600 Subject: btrfsutil: OldRebuiltForrest: Pull the cbs.Item nil check out of the loop --- lib/btrfsutil/old_rebuilt_forrest.go | 27 ++++++++++++++------------- 1 file changed, 14 insertions(+), 13 deletions(-) (limited to 'lib') diff --git a/lib/btrfsutil/old_rebuilt_forrest.go b/lib/btrfsutil/old_rebuilt_forrest.go index 6014793..08a204f 100644 --- a/lib/btrfsutil/old_rebuilt_forrest.go +++ b/lib/btrfsutil/old_rebuilt_forrest.go @@ -295,6 +295,9 @@ func (bt *OldRebuiltForrest) TreeWalk(ctx context.Context, treeID btrfsprim.ObjI }) return } + if cbs.Item == nil { + return + } var node *diskio.Ref[btrfsvol.LogicalAddr, btrfstree.Node] tree.Items.Range(func(indexItem *containers.RBNode[oldRebuiltTreeValue]) bool { if ctx.Err() != nil { @@ -303,23 +306,21 @@ func (bt *OldRebuiltForrest) TreeWalk(ctx context.Context, treeID btrfsprim.ObjI 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 + 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) - 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).FromItemSlot] - if err := cbs.Item(itemPath, item); err != nil { errHandle(&btrfstree.TreeError{Path: itemPath, Err: err}) + return true } } + item := node.Data.BodyLeaf[itemPath.Node(-1).FromItemSlot] + if err := cbs.Item(itemPath, item); err != nil { + errHandle(&btrfstree.TreeError{Path: itemPath, Err: err}) + } return true }) btrfstree.FreeNodeRef(node) -- cgit v1.2.3-2-g168b From 06aaeed9f20d3eddc30273ea8365db82331db262 Mon Sep 17 00:00:00 2001 From: Luke Shumaker Date: Mon, 13 Mar 2023 23:17:26 -0600 Subject: btrfsutil: OldRebuiltForrest: Fuss with indentation in rawTreeWalk --- lib/btrfsutil/old_rebuilt_forrest.go | 61 ++++++++++++++++++------------------ 1 file changed, 30 insertions(+), 31 deletions(-) (limited to 'lib') diff --git a/lib/btrfsutil/old_rebuilt_forrest.go b/lib/btrfsutil/old_rebuilt_forrest.go index 08a204f..af2643a 100644 --- a/lib/btrfsutil/old_rebuilt_forrest.go +++ b/lib/btrfsutil/old_rebuilt_forrest.go @@ -153,40 +153,39 @@ func (bt *OldRebuiltForrest) RebuiltTree(treeID btrfsprim.ObjID) oldRebuiltTree } 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)) + errHandle := 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, + }) + } + + cbs := 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.Errors.Insert(oldRebuiltTreeError{ - Path: bt.arena.Deflate(err.Path), - Err: err.Err, + 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 }, - 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 - }, - }, - ) + } + + btrfstree.TreeOperatorImpl{NodeSource: bt.inner}.RawTreeWalk(bt.ctx, root, errHandle, cbs) } func (bt *OldRebuiltForrest) TreeLookup(treeID btrfsprim.ObjID, key btrfsprim.Key) (btrfstree.Item, error) { -- cgit v1.2.3-2-g168b From cd1a18b54316da20482f3d1765319d69fcbd852a Mon Sep 17 00:00:00 2001 From: Luke Shumaker Date: Mon, 13 Mar 2023 16:41:57 -0600 Subject: btrfs: io3_btree.go: Organize the file --- lib/btrfs/io3_btree.go | 46 ++++++++++++++++++++++++++++++++-------------- 1 file changed, 32 insertions(+), 14 deletions(-) (limited to 'lib') diff --git a/lib/btrfs/io3_btree.go b/lib/btrfs/io3_btree.go index 18df98e..426e4a1 100644 --- a/lib/btrfs/io3_btree.go +++ b/lib/btrfs/io3_btree.go @@ -14,23 +14,18 @@ import ( "git.lukeshu.com/btrfs-progs-ng/lib/diskio" ) -func (fs *FS) TreeWalk(ctx context.Context, treeID btrfsprim.ObjID, errHandle func(*btrfstree.TreeError), cbs btrfstree.TreeWalkHandler) { - btrfstree.TreeOperatorImpl{NodeSource: fs}.TreeWalk(ctx, treeID, errHandle, cbs) -} +// This file is ordered from low-level to high-level. -func (fs *FS) TreeLookup(treeID btrfsprim.ObjID, key btrfsprim.Key) (btrfstree.Item, error) { - return btrfstree.TreeOperatorImpl{NodeSource: fs}.TreeLookup(treeID, key) -} +// btrfstree.NodeSource //////////////////////////////////////////////////////// -func (fs *FS) TreeSearch(treeID btrfsprim.ObjID, fn func(key btrfsprim.Key, size uint32) int) (btrfstree.Item, error) { - return btrfstree.TreeOperatorImpl{NodeSource: fs}.TreeSearch(treeID, fn) +// ReadNode implements btrfstree.NodeSource. +func (fs *FS) ReadNode(path btrfstree.TreePath) (*diskio.Ref[btrfsvol.LogicalAddr, btrfstree.Node], error) { + return btrfstree.FSReadNode(fs, path) } -func (fs *FS) TreeSearchAll(treeID btrfsprim.ObjID, fn func(key btrfsprim.Key, size uint32) int) ([]btrfstree.Item, error) { - return btrfstree.TreeOperatorImpl{NodeSource: fs}.TreeSearchAll(treeID, fn) -} +var _ btrfstree.NodeSource = (*FS)(nil) -var _ btrfstree.TreeOperator = (*FS)(nil) +// btrfstree.NodeFile ////////////////////////////////////////////////////////// func (fs *FS) populateTreeUUIDs(ctx context.Context) { if fs.cacheObjID2UUID == nil || fs.cacheUUID2ObjID == nil || fs.cacheTreeParent == nil { @@ -57,6 +52,7 @@ func (fs *FS) populateTreeUUIDs(ctx context.Context) { } } +// ParentTree implements btrfstree.NodeFile. func (fs *FS) ParentTree(tree btrfsprim.ObjID) (btrfsprim.ObjID, bool) { if tree < btrfsprim.FIRST_FREE_OBJECTID || tree > btrfsprim.LAST_FREE_OBJECTID { // no parent @@ -80,6 +76,28 @@ func (fs *FS) ParentTree(tree btrfsprim.ObjID) (btrfsprim.ObjID, bool) { return parentObjID, true } -func (fs *FS) ReadNode(path btrfstree.TreePath) (*diskio.Ref[btrfsvol.LogicalAddr, btrfstree.Node], error) { - return btrfstree.FSReadNode(fs, path) +var _ btrfstree.NodeFile = (*FS)(nil) + +// btrfstree.TreeOperator ////////////////////////////////////////////////////// + +// TreeWalk implements btrfstree.TreeOperator. +func (fs *FS) TreeWalk(ctx context.Context, treeID btrfsprim.ObjID, errHandle func(*btrfstree.TreeError), cbs btrfstree.TreeWalkHandler) { + btrfstree.TreeOperatorImpl{NodeSource: fs}.TreeWalk(ctx, treeID, errHandle, cbs) } + +// TreeLookup implements btrfstree.TreeOperator. +func (fs *FS) TreeLookup(treeID btrfsprim.ObjID, key btrfsprim.Key) (btrfstree.Item, error) { + return btrfstree.TreeOperatorImpl{NodeSource: fs}.TreeLookup(treeID, key) +} + +// TreeSearch implements btrfstree.TreeOperator. +func (fs *FS) TreeSearch(treeID btrfsprim.ObjID, fn func(key btrfsprim.Key, size uint32) int) (btrfstree.Item, error) { + return btrfstree.TreeOperatorImpl{NodeSource: fs}.TreeSearch(treeID, fn) +} + +// TreeSearchAll implements btrfstree.TreeOperator. +func (fs *FS) TreeSearchAll(treeID btrfsprim.ObjID, fn func(key btrfsprim.Key, size uint32) int) ([]btrfstree.Item, error) { + return btrfstree.TreeOperatorImpl{NodeSource: fs}.TreeSearchAll(treeID, fn) +} + +var _ btrfstree.TreeOperator = (*FS)(nil) -- cgit v1.2.3-2-g168b From 0733161bf46a279f11e20f9ffd34e0136c13a884 Mon Sep 17 00:00:00 2001 From: Luke Shumaker Date: Mon, 13 Mar 2023 18:52:51 -0600 Subject: btrfs: io3_btree.go: De-nest populateTreeUUIDs --- lib/btrfs/io3_btree.go | 41 +++++++++++++++++++++-------------------- 1 file changed, 21 insertions(+), 20 deletions(-) (limited to 'lib') diff --git a/lib/btrfs/io3_btree.go b/lib/btrfs/io3_btree.go index 426e4a1..db4e42c 100644 --- a/lib/btrfs/io3_btree.go +++ b/lib/btrfs/io3_btree.go @@ -28,28 +28,29 @@ var _ btrfstree.NodeSource = (*FS)(nil) // btrfstree.NodeFile ////////////////////////////////////////////////////////// func (fs *FS) populateTreeUUIDs(ctx context.Context) { - if fs.cacheObjID2UUID == nil || fs.cacheUUID2ObjID == nil || fs.cacheTreeParent == nil { - fs.cacheObjID2UUID = make(map[btrfsprim.ObjID]btrfsprim.UUID) - fs.cacheUUID2ObjID = make(map[btrfsprim.UUID]btrfsprim.ObjID) - fs.cacheTreeParent = make(map[btrfsprim.ObjID]btrfsprim.UUID) - fs.TreeWalk(ctx, btrfsprim.ROOT_TREE_OBJECTID, - func(err *btrfstree.TreeError) { - // do nothing - }, - btrfstree.TreeWalkHandler{ - Item: func(_ btrfstree.TreePath, item btrfstree.Item) error { - itemBody, ok := item.Body.(*btrfsitem.Root) - if !ok { - return nil - } - fs.cacheObjID2UUID[item.Key.ObjectID] = itemBody.UUID - fs.cacheTreeParent[item.Key.ObjectID] = itemBody.ParentUUID - fs.cacheUUID2ObjID[itemBody.UUID] = item.Key.ObjectID + if fs.cacheObjID2UUID != nil && fs.cacheUUID2ObjID != nil && fs.cacheTreeParent != nil { + return + } + fs.cacheObjID2UUID = make(map[btrfsprim.ObjID]btrfsprim.UUID) + fs.cacheUUID2ObjID = make(map[btrfsprim.UUID]btrfsprim.ObjID) + fs.cacheTreeParent = make(map[btrfsprim.ObjID]btrfsprim.UUID) + fs.TreeWalk(ctx, btrfsprim.ROOT_TREE_OBJECTID, + func(err *btrfstree.TreeError) { + // do nothing + }, + btrfstree.TreeWalkHandler{ + Item: func(_ btrfstree.TreePath, item btrfstree.Item) error { + itemBody, ok := item.Body.(*btrfsitem.Root) + if !ok { return nil - }, + } + fs.cacheObjID2UUID[item.Key.ObjectID] = itemBody.UUID + fs.cacheTreeParent[item.Key.ObjectID] = itemBody.ParentUUID + fs.cacheUUID2ObjID[itemBody.UUID] = item.Key.ObjectID + return nil }, - ) - } + }, + ) } // ParentTree implements btrfstree.NodeFile. -- cgit v1.2.3-2-g168b From bb9dafebfbf3bfd6ea111c88371844f3402f3f3f Mon Sep 17 00:00:00 2001 From: Luke Shumaker Date: Sat, 4 Mar 2023 11:21:43 -0700 Subject: btrfsutil: Rebuiltforrest: Update obsolete references to LRUCache in comments --- lib/btrfsutil/rebuilt_tree.go | 6 +++--- 1 file changed, 3 insertions(+), 3 deletions(-) (limited to 'lib') diff --git a/lib/btrfsutil/rebuilt_tree.go b/lib/btrfsutil/rebuilt_tree.go index 9e23074..3133a9e 100644 --- a/lib/btrfsutil/rebuilt_tree.go +++ b/lib/btrfsutil/rebuilt_tree.go @@ -33,7 +33,7 @@ type RebuiltTree struct { 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 + // `mu`; but they live in a shared ARCache. They are all // derived from tree.Roots, which is why it's OK if they get // evicted. // @@ -42,7 +42,7 @@ type RebuiltTree struct { // 3. tree.PotentialItems() = tree.forrest.excItems.Load(tree.ID) } -// LRU member 1: .leafToRoots() //////////////////////////////////////////////////////////////////////////////////////// +// evictable member 1: .leafToRoots() ////////////////////////////////////////////////////////////////////////////////// // leafToRoots returns all leafs (lvl=0) in the filesystem that pass // .isOwnerOK, whether or not they're in the tree. @@ -129,7 +129,7 @@ func (tree *RebuiltTree) isOwnerOK(owner btrfsprim.ObjID, gen btrfsprim.Generati } } -// LRU members 2 and 3: .Items() and .PotentialItems() ///////////////////////////////////////////////////////////////// +// evictable members 2 and 3: .Items() and .PotentialItems() /////////////////////////////////////////////////////////// // Items returns a map of the items contained in this tree. // -- cgit v1.2.3-2-g168b