summaryrefslogtreecommitdiff
path: root/lib/btrfs
diff options
context:
space:
mode:
Diffstat (limited to 'lib/btrfs')
-rw-r--r--lib/btrfs/btrfstree/btree_forrest.go4
-rw-r--r--lib/btrfs/btrfstree/btree_tree.go120
-rw-r--r--lib/btrfs/btrfstree/path.go22
-rw-r--r--lib/btrfs/btrfstree/types_node.go32
-rw-r--r--lib/btrfs/io3_btree.go87
5 files changed, 142 insertions, 123 deletions
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..e75eb0b 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 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 btrfsprim nodes
+ // Callbacks for items on interior 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,12 +110,12 @@ 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,
- FromItemIdx: -1,
+ FromItemSlot: -1,
ToNodeAddr: rootInfo.RootNode,
ToNodeGeneration: rootInfo.Generation,
ToNodeLevel: rootInfo.Level,
@@ -169,14 +169,14 @@ 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,
- 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,
@@ -261,9 +261,9 @@ func (fs TreeOperatorImpl) treeSearch(treeRoot TreeRoot, fn func(btrfsprim.Key,
}
if node.Data.Head.Level > 0 {
- // btrfsprim 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,
+ FromItemSlot: lastGood,
+ 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)
@@ -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.BodyInternal[path.Node(-1).FromItemIdx].BlockPtr
+ path.Node(-1).ToNodeAddr = node.Data.BodyInterior[path.Node(-1).FromItemSlot].BlockPtr
}
}
// go down
@@ -360,19 +360,19 @@ 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,
+ 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,
- 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 {
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.BodyInternal[path.Node(-1).FromItemIdx].BlockPtr
+ path.Node(-1).ToNodeAddr = node.Data.BodyInterior[path.Node(-1).FromItemSlot].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,
+ FromItemSlot: 0,
+ 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,
+ FromTree: node.Data.Head.Owner,
+ FromItemSlot: 0,
+ ToKey: node.Data.BodyInterior[0].Key,
+ ToMaxKey: node.Data.BodyInterior[0].Key,
})
}
}
@@ -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 {
@@ -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
@@ -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 {
@@ -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 <lukeshu@lukeshu.com>
+// Copyright (C) 2022-2023 Luke Shumaker <lukeshu@lukeshu.com>
//
// 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/btrfs/btrfstree/types_node.go b/lib/btrfs/btrfstree/types_node.go
index 0a89e05..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 btrfsprim 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 btrfsprim 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/btrfs/io3_btree.go b/lib/btrfs/io3_btree.go
index 18df98e..db4e42c 100644
--- a/lib/btrfs/io3_btree.go
+++ b/lib/btrfs/io3_btree.go
@@ -14,49 +14,46 @@ 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 {
- 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.
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 +77,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)
generated by cgit v1.2.3-54-g00ecf (git 2.45.2) at 2024-11-19 12:47:48 +0000