summaryrefslogtreecommitdiff
path: root/lib/btrfs
diff options
context:
space:
mode:
Diffstat (limited to 'lib/btrfs')
-rw-r--r--lib/btrfs/btrfstree/ops.go25
-rw-r--r--lib/btrfs/btrfstree/path.go6
-rw-r--r--lib/btrfs/btrfstree/readnode.go54
-rw-r--r--lib/btrfs/btrfstree/root.go2
-rw-r--r--lib/btrfs/btrfstree/types_node.go10
-rw-r--r--lib/btrfs/io3_btree.go64
-rw-r--r--lib/btrfs/io4_fs.go2
7 files changed, 100 insertions, 63 deletions
diff --git a/lib/btrfs/btrfstree/ops.go b/lib/btrfs/btrfstree/ops.go
index 83c08c4..02511f5 100644
--- a/lib/btrfs/btrfstree/ops.go
+++ b/lib/btrfs/btrfstree/ops.go
@@ -20,7 +20,8 @@ import (
"git.lukeshu.com/btrfs-progs-ng/lib/slices"
)
-type Trees interface {
+// TreeOperator is an interface for performing basic btree operations.
+type TreeOperator interface {
// TreeWalk walks a tree, triggering callbacks for every node,
// key-pointer, and item; as well as for any errors encountered.
//
@@ -91,12 +92,12 @@ type NodeSource interface {
ReadNode(TreePath) (*diskio.Ref[btrfsvol.LogicalAddr, Node], error)
}
-type TreesImpl struct {
+type TreeOperatorImpl struct {
NodeSource
}
// TreeWalk implements the 'Trees' interface.
-func (fs TreesImpl) TreeWalk(ctx context.Context, treeID btrfsprim.ObjID, errHandle func(*TreeError), cbs TreeWalkHandler) {
+func (fs TreeOperatorImpl) TreeWalk(ctx context.Context, treeID btrfsprim.ObjID, errHandle func(*TreeError), cbs TreeWalkHandler) {
sb, err := fs.Superblock()
if err != nil {
errHandle(&TreeError{Path: TreePath{{FromTree: treeID}}, Err: err})
@@ -109,9 +110,9 @@ func (fs TreesImpl) TreeWalk(ctx context.Context, treeID btrfsprim.ObjID, errHan
fs.RawTreeWalk(ctx, *rootInfo, errHandle, cbs)
}
-// TreeWalk is a utility function to help with implementing the 'Trees'
+// TreeWalk is a utility method to help with implementing the 'Trees'.
// interface.
-func (fs TreesImpl) RawTreeWalk(ctx context.Context, rootInfo TreeRoot, errHandle func(*TreeError), cbs TreeWalkHandler) {
+func (fs TreeOperatorImpl) RawTreeWalk(ctx context.Context, rootInfo TreeRoot, errHandle func(*TreeError), cbs TreeWalkHandler) {
path := TreePath{{
FromTree: rootInfo.TreeID,
FromGeneration: rootInfo.Generation,
@@ -122,7 +123,7 @@ func (fs TreesImpl) RawTreeWalk(ctx context.Context, rootInfo TreeRoot, errHandl
fs.treeWalk(ctx, path, errHandle, cbs)
}
-func (fs TreesImpl) treeWalk(ctx context.Context, path TreePath, errHandle func(*TreeError), cbs TreeWalkHandler) {
+func (fs TreeOperatorImpl) treeWalk(ctx context.Context, path TreePath, errHandle func(*TreeError), cbs TreeWalkHandler) {
if ctx.Err() != nil {
return
}
@@ -233,7 +234,7 @@ func (fs TreesImpl) treeWalk(ctx context.Context, path TreePath, errHandle func(
}
}
-func (fs TreesImpl) treeSearch(treeRoot TreeRoot, fn func(btrfsprim.Key, uint32) int) (TreePath, *diskio.Ref[btrfsvol.LogicalAddr, Node], error) {
+func (fs TreeOperatorImpl) treeSearch(treeRoot TreeRoot, fn func(btrfsprim.Key, uint32) int) (TreePath, *diskio.Ref[btrfsvol.LogicalAddr, Node], error) {
path := TreePath{{
FromTree: treeRoot.TreeID,
FromGeneration: treeRoot.Generation,
@@ -303,7 +304,7 @@ func (fs TreesImpl) treeSearch(treeRoot TreeRoot, fn func(btrfsprim.Key, uint32)
}
}
-func (fs TreesImpl) prev(path TreePath, node *diskio.Ref[btrfsvol.LogicalAddr, Node]) (TreePath, *diskio.Ref[btrfsvol.LogicalAddr, Node], error) {
+func (fs TreeOperatorImpl) prev(path TreePath, node *diskio.Ref[btrfsvol.LogicalAddr, Node]) (TreePath, *diskio.Ref[btrfsvol.LogicalAddr, Node], error) {
var err error
path = path.DeepCopy()
@@ -359,7 +360,7 @@ func (fs TreesImpl) prev(path TreePath, node *diskio.Ref[btrfsvol.LogicalAddr, N
return path, node, nil
}
-func (fs TreesImpl) next(path TreePath, node *diskio.Ref[btrfsvol.LogicalAddr, Node]) (TreePath, *diskio.Ref[btrfsvol.LogicalAddr, Node], error) {
+func (fs TreeOperatorImpl) next(path TreePath, node *diskio.Ref[btrfsvol.LogicalAddr, Node]) (TreePath, *diskio.Ref[btrfsvol.LogicalAddr, Node], error) {
var err error
path = path.DeepCopy()
@@ -431,7 +432,7 @@ func (fs TreesImpl) next(path TreePath, node *diskio.Ref[btrfsvol.LogicalAddr, N
}
// TreeSearch implements the 'Trees' interface.
-func (fs TreesImpl) TreeSearch(treeID btrfsprim.ObjID, fn func(btrfsprim.Key, uint32) int) (Item, error) {
+func (fs TreeOperatorImpl) TreeSearch(treeID btrfsprim.ObjID, fn func(btrfsprim.Key, uint32) int) (Item, error) {
sb, err := fs.Superblock()
if err != nil {
return Item{}, err
@@ -455,7 +456,7 @@ func KeySearch(fn func(btrfsprim.Key) int) func(btrfsprim.Key, uint32) int {
}
// TreeLookup implements the 'Trees' interface.
-func (fs TreesImpl) TreeLookup(treeID btrfsprim.ObjID, key btrfsprim.Key) (Item, error) {
+func (fs TreeOperatorImpl) TreeLookup(treeID btrfsprim.ObjID, key btrfsprim.Key) (Item, error) {
item, err := fs.TreeSearch(treeID, KeySearch(key.Cmp))
if err != nil {
err = fmt.Errorf("item with key=%v: %w", key, err)
@@ -464,7 +465,7 @@ func (fs TreesImpl) TreeLookup(treeID btrfsprim.ObjID, key btrfsprim.Key) (Item,
}
// TreeSearchAll implements the 'Trees' interface.
-func (fs TreesImpl) TreeSearchAll(treeID btrfsprim.ObjID, fn func(btrfsprim.Key, uint32) int) ([]Item, error) {
+func (fs TreeOperatorImpl) TreeSearchAll(treeID btrfsprim.ObjID, fn func(btrfsprim.Key, uint32) int) ([]Item, error) {
sb, err := fs.Superblock()
if err != nil {
return nil, err
diff --git a/lib/btrfs/btrfstree/path.go b/lib/btrfs/btrfstree/path.go
index 99461a4..4a4d66e 100644
--- a/lib/btrfs/btrfstree/path.go
+++ b/lib/btrfs/btrfstree/path.go
@@ -14,7 +14,11 @@ import (
"git.lukeshu.com/btrfs-progs-ng/lib/btrfs/btrfsvol"
)
-// - The first element will always have an ItemIdx of -1.
+// TreePath is a path from the superblock (i.e. the root of the btrfs
+// 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.
//
// - For .Item() callbacks, the last element will always have a
// NodeAddr of 0.
diff --git a/lib/btrfs/btrfstree/readnode.go b/lib/btrfs/btrfstree/readnode.go
new file mode 100644
index 0000000..bb80d20
--- /dev/null
+++ b/lib/btrfs/btrfstree/readnode.go
@@ -0,0 +1,54 @@
+// Copyright (C) 2022 Luke Shumaker <lukeshu@lukeshu.com>
+//
+// SPDX-License-Identifier: GPL-2.0-or-later
+
+package btrfstree
+
+import (
+ "fmt"
+
+ "git.lukeshu.com/btrfs-progs-ng/lib/btrfs/btrfsprim"
+ "git.lukeshu.com/btrfs-progs-ng/lib/btrfs/btrfsvol"
+ "git.lukeshu.com/btrfs-progs-ng/lib/containers"
+ "git.lukeshu.com/btrfs-progs-ng/lib/diskio"
+)
+
+// FSReadNode is a utility function to help with implementing the
+// 'NodeSource' interface.
+func FSReadNode(
+ fs interface {
+ diskio.File[btrfsvol.LogicalAddr]
+ Superblock() (*Superblock, error)
+ ParentTree(btrfsprim.ObjID) (btrfsprim.ObjID, bool)
+ },
+ path TreePath,
+) (*diskio.Ref[btrfsvol.LogicalAddr, Node], error) {
+ sb, err := fs.Superblock()
+ if err != nil {
+ return nil, fmt.Errorf("btrfs.FS.ReadNode: %w", err)
+ }
+
+ var treeParents []btrfsprim.ObjID
+ checkOwner := func(owner btrfsprim.ObjID) error {
+ exp := path.Node(-1).FromTree
+ for {
+ if owner == exp {
+ return nil
+ }
+ treeParents = append(treeParents, exp)
+ var ok bool
+ exp, ok = fs.ParentTree(exp)
+ if !ok {
+ return fmt.Errorf("expected owner in %v but claims to have owner=%v",
+ treeParents, owner)
+ }
+ }
+ }
+
+ return ReadNode[btrfsvol.LogicalAddr](fs, *sb, path.Node(-1).ToNodeAddr, NodeExpectations{
+ LAddr: containers.Optional[btrfsvol.LogicalAddr]{OK: true, Val: path.Node(-1).ToNodeAddr},
+ Level: containers.Optional[uint8]{OK: true, Val: path.Node(-1).ToNodeLevel},
+ MaxGeneration: containers.Optional[btrfsprim.Generation]{OK: true, Val: path.Node(-1).FromGeneration},
+ Owner: checkOwner,
+ })
+}
diff --git a/lib/btrfs/btrfstree/root.go b/lib/btrfs/btrfstree/root.go
index 41aac69..a233ef0 100644
--- a/lib/btrfs/btrfstree/root.go
+++ b/lib/btrfs/btrfstree/root.go
@@ -23,7 +23,7 @@ type TreeRoot struct {
// LookupTreeRoot is a utility function to help with implementing the 'Trees'
// interface.
-func LookupTreeRoot(fs Trees, sb Superblock, treeID btrfsprim.ObjID) (*TreeRoot, error) {
+func LookupTreeRoot(fs TreeOperator, sb Superblock, treeID btrfsprim.ObjID) (*TreeRoot, error) {
switch treeID {
case btrfsprim.ROOT_TREE_OBJECTID:
return &TreeRoot{
diff --git a/lib/btrfs/btrfstree/types_node.go b/lib/btrfs/btrfstree/types_node.go
index aecdf9c..6718fbe 100644
--- a/lib/btrfs/btrfstree/types_node.go
+++ b/lib/btrfs/btrfstree/types_node.go
@@ -17,7 +17,6 @@ import (
"git.lukeshu.com/btrfs-progs-ng/lib/containers"
"git.lukeshu.com/btrfs-progs-ng/lib/diskio"
"git.lukeshu.com/btrfs-progs-ng/lib/fmtutil"
- "git.lukeshu.com/btrfs-progs-ng/lib/slices"
)
type NodeFlags uint64
@@ -386,7 +385,7 @@ type NodeExpectations struct {
// Things knowable from the parent.
Level containers.Optional[uint8]
MaxGeneration containers.Optional[btrfsprim.Generation]
- Owner []btrfsprim.ObjID
+ Owner func(btrfsprim.ObjID) error
}
func ReadNode[Addr ~int64](fs diskio.File[Addr], sb Superblock, addr Addr, exp NodeExpectations) (*diskio.Ref[Addr, Node], error) {
@@ -437,9 +436,10 @@ func ReadNode[Addr ~int64](fs diskio.File[Addr], sb Superblock, addr Addr, exp N
return nodeRef, fmt.Errorf("btrfs.ReadNode: node@%v: expected generation<=%v but claims to be generation=%v",
addr, exp.MaxGeneration.Val, nodeRef.Data.Head.Generation)
}
- if len(exp.Owner) > 0 && !slices.Contains(nodeRef.Data.Head.Owner, exp.Owner) {
- return nodeRef, fmt.Errorf("btrfs.ReadNode: node@%v: expected owner in %v but claims to have owner=%v",
- addr, exp.Owner, nodeRef.Data.Head.Owner)
+ if exp.Owner != nil {
+ if err := exp.Owner(nodeRef.Data.Head.Owner); err != nil {
+ return nodeRef, fmt.Errorf("btrfs.ReadNode: node@%v: %w", addr, err)
+ }
}
// parse (main)
diff --git a/lib/btrfs/io3_btree.go b/lib/btrfs/io3_btree.go
index 31cf857..8455eee 100644
--- a/lib/btrfs/io3_btree.go
+++ b/lib/btrfs/io3_btree.go
@@ -6,7 +6,6 @@ package btrfs
import (
"context"
- "fmt"
"github.com/datawire/dlib/dlog"
@@ -14,24 +13,23 @@ import (
"git.lukeshu.com/btrfs-progs-ng/lib/btrfs/btrfsprim"
"git.lukeshu.com/btrfs-progs-ng/lib/btrfs/btrfstree"
"git.lukeshu.com/btrfs-progs-ng/lib/btrfs/btrfsvol"
- "git.lukeshu.com/btrfs-progs-ng/lib/containers"
"git.lukeshu.com/btrfs-progs-ng/lib/diskio"
)
func (fs *FS) TreeWalk(ctx context.Context, treeID btrfsprim.ObjID, errHandle func(*btrfstree.TreeError), cbs btrfstree.TreeWalkHandler) {
- btrfstree.TreesImpl{NodeSource: fs}.TreeWalk(ctx, treeID, errHandle, cbs)
+ btrfstree.TreeOperatorImpl{NodeSource: fs}.TreeWalk(ctx, treeID, errHandle, cbs)
}
func (fs *FS) TreeLookup(treeID btrfsprim.ObjID, key btrfsprim.Key) (btrfstree.Item, error) {
- return btrfstree.TreesImpl{NodeSource: fs}.TreeLookup(treeID, key)
+ return btrfstree.TreeOperatorImpl{NodeSource: fs}.TreeLookup(treeID, key)
}
func (fs *FS) TreeSearch(treeID btrfsprim.ObjID, fn func(key btrfsprim.Key, size uint32) int) (btrfstree.Item, error) {
- return btrfstree.TreesImpl{NodeSource: fs}.TreeSearch(treeID, fn)
+ return btrfstree.TreeOperatorImpl{NodeSource: fs}.TreeSearch(treeID, fn)
}
func (fs *FS) TreeSearchAll(treeID btrfsprim.ObjID, fn func(key btrfsprim.Key, size uint32) int) ([]btrfstree.Item, error) {
- return btrfstree.TreesImpl{NodeSource: fs}.TreeSearchAll(treeID, fn)
+ return btrfstree.TreeOperatorImpl{NodeSource: fs}.TreeSearchAll(treeID, fn)
}
-var _ btrfstree.Trees = (*FS)(nil)
+var _ btrfstree.TreeOperator = (*FS)(nil)
func (fs *FS) populateTreeUUIDs(ctx context.Context) {
if fs.cacheObjID2UUID == nil || fs.cacheUUID2ObjID == nil || fs.cacheTreeParent == nil {
@@ -59,44 +57,24 @@ func (fs *FS) populateTreeUUIDs(ctx context.Context) {
}
}
-var noParents = make(map[btrfsprim.ObjID]struct{})
-
-func (fs *FS) ReadNode(path btrfstree.TreePath) (*diskio.Ref[btrfsvol.LogicalAddr, btrfstree.Node], error) {
- sb, err := fs.Superblock()
- if err != nil {
- return nil, fmt.Errorf("btrfs.FS.ReadNode: %w", err)
+func (fs *FS) ParentTree(tree btrfsprim.ObjID) (btrfsprim.ObjID, bool) {
+ ctx := context.TODO()
+ if tree < btrfsprim.FIRST_FREE_OBJECTID {
+ return 0, false
}
-
- potentialOwners := []btrfsprim.ObjID{
- path.Node(-1).FromTree,
+ fs.populateTreeUUIDs(ctx)
+ parentUUID := fs.cacheTreeParent[tree]
+ if parentUUID == (btrfsprim.UUID{}) {
+ return 0, false
}
- if potentialOwners[0] >= btrfsprim.FIRST_FREE_OBJECTID {
- ctx := context.TODO()
- fs.populateTreeUUIDs(ctx)
- for potentialOwners[len(potentialOwners)-1] >= btrfsprim.FIRST_FREE_OBJECTID {
- objID := potentialOwners[len(potentialOwners)-1]
- parentUUID := fs.cacheTreeParent[objID]
- if parentUUID == (btrfsprim.UUID{}) {
- if _, already := noParents[objID]; !already {
- dlog.Infof(ctx, "dbg: objID=%v has no parent", objID)
- noParents[objID] = struct{}{}
- }
- break
- }
- dlog.Infof(ctx, "dbg: parent of objID=%v is %v", objID, parentUUID)
- parentObjID, ok := fs.cacheUUID2ObjID[parentUUID]
- if !ok {
- dlog.Errorf(ctx, "dbg: could not resolve parentUUID=%v to an ObjID", parentUUID)
- break
- }
- potentialOwners = append(potentialOwners, parentObjID)
- }
+ parentObjID, ok := fs.cacheUUID2ObjID[parentUUID]
+ if !ok {
+ dlog.Errorf(ctx, "dbg: could not resolve parentUUID=%v to an ObjID", parentUUID)
+ return 0, false
}
+ return parentObjID, true
+}
- return btrfstree.ReadNode[btrfsvol.LogicalAddr](fs, *sb, path.Node(-1).ToNodeAddr, btrfstree.NodeExpectations{
- LAddr: containers.Optional[btrfsvol.LogicalAddr]{OK: true, Val: path.Node(-1).ToNodeAddr},
- Level: containers.Optional[uint8]{OK: true, Val: path.Node(-1).ToNodeLevel},
- MaxGeneration: containers.Optional[btrfsprim.Generation]{OK: true, Val: path.Node(-1).FromGeneration},
- Owner: potentialOwners,
- })
+func (fs *FS) ReadNode(path btrfstree.TreePath) (*diskio.Ref[btrfsvol.LogicalAddr, btrfstree.Node], error) {
+ return btrfstree.FSReadNode(fs, path)
}
diff --git a/lib/btrfs/io4_fs.go b/lib/btrfs/io4_fs.go
index 7bfcc00..8751078 100644
--- a/lib/btrfs/io4_fs.go
+++ b/lib/btrfs/io4_fs.go
@@ -61,7 +61,7 @@ type File struct {
type Subvolume struct {
FS interface {
- btrfstree.Trees
+ btrfstree.TreeOperator
Superblock() (*btrfstree.Superblock, error)
ReadAt(p []byte, off btrfsvol.LogicalAddr) (int, error)
}
generated by cgit v1.2.3-2-g168b (git 2.25.1) at 2025-03-21 05:18:09 +0000