From 8aea2c35c9475293c89293a148134c0e6d5c4e7b Mon Sep 17 00:00:00 2001 From: Luke Shumaker Date: Sun, 28 Aug 2022 16:55:06 -0600 Subject: wip --- lib/btrfs/btrfstree/ops.go | 25 +++++++++--------- lib/btrfs/btrfstree/path.go | 6 ++++- lib/btrfs/btrfstree/readnode.go | 54 +++++++++++++++++++++++++++++++++++++++ lib/btrfs/btrfstree/root.go | 2 +- lib/btrfs/btrfstree/types_node.go | 10 ++++---- 5 files changed, 78 insertions(+), 19 deletions(-) create mode 100644 lib/btrfs/btrfstree/readnode.go (limited to 'lib/btrfs/btrfstree') 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 +// +// 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) -- cgit v1.2.3-54-g00ecf