From 8387d36fac1f01505b37d90d675609460202310d Mon Sep 17 00:00:00 2001 From: Luke Shumaker Date: Thu, 2 Mar 2023 16:42:32 -0700 Subject: btrfstree: Shuffle things between files --- lib/btrfs/btrfstree/btree.go | 86 ++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 86 insertions(+) create mode 100644 lib/btrfs/btrfstree/btree.go (limited to 'lib/btrfs/btrfstree/btree.go') diff --git a/lib/btrfs/btrfstree/btree.go b/lib/btrfs/btrfstree/btree.go new file mode 100644 index 0000000..2fd7c39 --- /dev/null +++ b/lib/btrfs/btrfstree/btree.go @@ -0,0 +1,86 @@ +// Copyright (C) 2022-2023 Luke Shumaker +// +// SPDX-License-Identifier: GPL-2.0-or-later + +package btrfstree + +import ( + "context" + "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/diskio" +) + +// 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. + // + // If the tree is valid, then everything is walked in key-order; but if + // the tree is broken, then ordering is not guaranteed. + // + // Canceling the Context causes TreeWalk to return early; no + // values from the Context are used. + // + // The lifecycle of callbacks is: + // + // 001 .PreNode() + // 002 (read node) + // 003 .Node() (or .BadNode()) + // for item in node.items: + // if interior: + // 004 .PreKeyPointer() + // 005 (recurse) + // 006 .PostKeyPointer() + // else: + // 004 .Item() (or .BadItem()) + // 007 .PostNode() + TreeWalk(ctx context.Context, treeID btrfsprim.ObjID, errHandle func(*TreeError), cbs TreeWalkHandler) + + TreeLookup(treeID btrfsprim.ObjID, key btrfsprim.Key) (Item, error) + TreeSearch(treeID btrfsprim.ObjID, fn func(key btrfsprim.Key, size uint32) int) (Item, error) // size is math.MaxUint32 for key-pointers + + // If some items are able to be read, but there is an error reading the + // full set, then it might return *both* a list of items and an error. + // + // If no such item is found, an error that is io/fs.ErrNotExist is + // returned. + TreeSearchAll(treeID btrfsprim.ObjID, fn func(key btrfsprim.Key, size uint32) int) ([]Item, error) // size is math.MaxUint32 for key-pointers +} + +type TreeWalkHandler struct { + // Callbacks for entire nodes. + // + // If any of these return an error that is io/fs.SkipDir, the + // node immediately stops getting processed; if PreNode, Node, + // or BadNode return io/fs.SkipDir then key pointers and items + // within the node are not processed. + PreNode func(TreePath) error + 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 interior nodes + PreKeyPointer func(TreePath, KeyPointer) error + PostKeyPointer func(TreePath, KeyPointer) error + // Callbacks for items on leaf nodes + Item func(TreePath, Item) error + BadItem func(TreePath, Item) error +} + +type TreeError struct { + Path TreePath + Err error +} + +func (e *TreeError) Unwrap() error { return e.Err } + +func (e *TreeError) Error() string { + return fmt.Sprintf("%v: %v", e.Path, e.Err) +} + +type NodeSource interface { + Superblock() (*Superblock, error) + ReadNode(TreePath) (*diskio.Ref[btrfsvol.LogicalAddr, Node], error) +} -- cgit v1.2.3-2-g168b From 56e44b0630448d44f7aa7f85b2098007ddbae06f Mon Sep 17 00:00:00 2001 From: Luke Shumaker Date: Wed, 15 Mar 2023 15:17:11 -0600 Subject: btrfstree: Distinguish between tree-not-found and item-not-found --- lib/btrfs/btrfstree/btree.go | 5 ++++- 1 file changed, 4 insertions(+), 1 deletion(-) (limited to 'lib/btrfs/btrfstree/btree.go') diff --git a/lib/btrfs/btrfstree/btree.go b/lib/btrfs/btrfstree/btree.go index 2fd7c39..7b3721b 100644 --- a/lib/btrfs/btrfstree/btree.go +++ b/lib/btrfs/btrfstree/btree.go @@ -45,7 +45,10 @@ type TreeOperator interface { // If some items are able to be read, but there is an error reading the // full set, then it might return *both* a list of items and an error. // - // If no such item is found, an error that is io/fs.ErrNotExist is + // If the tree is not found, an error that is ErrNoTree is + // returned. + // + // If no such item is found, an error that is ErrNoItem is // returned. TreeSearchAll(treeID btrfsprim.ObjID, fn func(key btrfsprim.Key, size uint32) int) ([]Item, error) // size is math.MaxUint32 for key-pointers } -- cgit v1.2.3-2-g168b From d7e086766e0f4396f29987d3798cefc1bb675d1c Mon Sep 17 00:00:00 2001 From: Luke Shumaker Date: Wed, 15 Mar 2023 15:17:11 -0600 Subject: btrfstree: Have errors include context of what was being searched for --- lib/btrfs/btrfstree/btree.go | 13 +++++++++++-- 1 file changed, 11 insertions(+), 2 deletions(-) (limited to 'lib/btrfs/btrfstree/btree.go') diff --git a/lib/btrfs/btrfstree/btree.go b/lib/btrfs/btrfstree/btree.go index 7b3721b..4c10ffa 100644 --- a/lib/btrfs/btrfstree/btree.go +++ b/lib/btrfs/btrfstree/btree.go @@ -13,6 +13,15 @@ import ( "git.lukeshu.com/btrfs-progs-ng/lib/diskio" ) +type TreeSearcher interface { + // How the search should be described in the event of an + // error. + fmt.Stringer + + // size is math.MaxUint32 for key-pointers + Search(key btrfsprim.Key, size uint32) int +} + // TreeOperator is an interface for performing basic btree operations. type TreeOperator interface { // TreeWalk walks a tree, triggering callbacks for every node, @@ -40,7 +49,7 @@ type TreeOperator interface { TreeWalk(ctx context.Context, treeID btrfsprim.ObjID, errHandle func(*TreeError), cbs TreeWalkHandler) TreeLookup(treeID btrfsprim.ObjID, key btrfsprim.Key) (Item, error) - TreeSearch(treeID btrfsprim.ObjID, fn func(key btrfsprim.Key, size uint32) int) (Item, error) // size is math.MaxUint32 for key-pointers + TreeSearch(treeID btrfsprim.ObjID, search TreeSearcher) (Item, error) // If some items are able to be read, but there is an error reading the // full set, then it might return *both* a list of items and an error. @@ -50,7 +59,7 @@ type TreeOperator interface { // // If no such item is found, an error that is ErrNoItem is // returned. - TreeSearchAll(treeID btrfsprim.ObjID, fn func(key btrfsprim.Key, size uint32) int) ([]Item, error) // size is math.MaxUint32 for key-pointers + TreeSearchAll(treeID btrfsprim.ObjID, search TreeSearcher) ([]Item, error) } type TreeWalkHandler struct { -- cgit v1.2.3-2-g168b