From 72b20c1d798551bfa2bb46f5521553144b45c09f Mon Sep 17 00:00:00 2001 From: Luke Shumaker Date: Thu, 2 Mar 2023 16:02:42 -0700 Subject: btrfstree: Rethink the API, but leave the old API in place --- lib/btrfs/btrfstree/btree.go | 84 +++++++++++++++++++++++++++++++++++ lib/btrfs/btrfstree/btree_forrest.go | 85 +++++++++++++++++++++++++++++------- lib/btrfs/btrfstree/btree_tree.go | 37 +++++++++++++++- 3 files changed, 189 insertions(+), 17 deletions(-) (limited to 'lib/btrfs/btrfstree') diff --git a/lib/btrfs/btrfstree/btree.go b/lib/btrfs/btrfstree/btree.go index 19c7c68..cbaa6d0 100644 --- a/lib/btrfs/btrfstree/btree.go +++ b/lib/btrfs/btrfstree/btree.go @@ -14,7 +14,62 @@ import ( "git.lukeshu.com/btrfs-progs-ng/lib/btrfs/btrfsvol" ) +type Forrest interface { + // ForrestLookup returns (nil, ErrNoTree) if the tree does not + // exist but there is otherwise no error. + ForrestLookup(ctx context.Context, treeID btrfsprim.ObjID) (Tree, error) +} + type Tree interface { + // TreeLookup looks up the Item for a given key. + // + // If no such Item exists, but there is otherwise no error, + // then ErrNoItem is returned. + TreeLookup(ctx context.Context, key btrfsprim.Key) (Item, error) + + // TreeSearch searches the Tree for a value for which + // `search.Search(itemKey, itemSize) == 0`. + // + // : + + + 0 0 0 - - - + // : ^ ^ ^ + // : any of + // + // You can conceptualize `search.Search` as subtraction: + // + // func(strawKey btrfsprim.Key, strawSize uint32) int { + // return needle - straw + // } + // + // `search.Search` may be called with key/size pairs that do not + // correspond to an existing Item (for key-pointers in + // interior nodes in the tree); in which case the size + // math.MaxUint32. + // + // If no such Item exists, but there is otherwise no error, + // then an error that is ErrNoItem is returned. + TreeSearch(ctx context.Context, search TreeSearcher) (Item, error) + + // TreeRange iterates over the Tree in order, calling + // `handleFn` for each Item. + TreeRange(ctx context.Context, handleFn func(Item) bool) error + + // TreeSubrange iterates over the Tree in order, calling + // `handleFn` for all Items for which `search.Search` returns + // 0. + // + // `search.Search` may be called with key/size pairs that do + // not correspond to an existing Item (for key-pointers in + // interior nodes in the tree); in which case the size + // math.MaxUint32. + // + // If handleFn is called for fewer than `min` items, an error + // that is ErrNoItem is returned. + TreeSubrange(ctx context.Context, + min int, + search TreeSearcher, + handleFn func(Item) bool, + ) error + // CheckOwner returns whether it is permissible for a node // with .Head.Owner=owner and .Head.Generation=gen to be in // this tree. @@ -23,6 +78,33 @@ type Tree interface { // specifies whether it should return an error (false) or nil // (true). TreeCheckOwner(ctx context.Context, failOpen bool, owner btrfsprim.ObjID, gen btrfsprim.Generation) error + + // TreeWalk is a lower-level call than TreeSubrange. Use with + // hesitancy. + // + // It 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: + // + // 000 (read superblock) (maybe cbs.BadSuperblock()) + // + // 001 (read node) + // 002 cbs.Node() or cbs.BadNode() + // if interior: + // for kp in node.items: + // 003a if cbs.PreKeyPointer == nil || cbs.PreKeyPointer() { + // 004b (recurse) + // else: + // for item in node.items: + // 003b cbs.Item() or cbs.BadItem() + TreeWalk(ctx context.Context, cbs TreeWalkHandler) } type TreeSearcher interface { @@ -55,6 +137,8 @@ type TreeWalkHandler struct { BadItem func(Path, Item) } +// Compat ////////////////////////////////////////////////////////////////////// + // TreeOperator is an interface for performing basic btree operations. type TreeOperator interface { // TreeWalk walks a tree, triggering callbacks for every node, diff --git a/lib/btrfs/btrfstree/btree_forrest.go b/lib/btrfs/btrfstree/btree_forrest.go index 1875c2f..4a4a4c0 100644 --- a/lib/btrfs/btrfstree/btree_forrest.go +++ b/lib/btrfs/btrfstree/btree_forrest.go @@ -14,6 +14,8 @@ import ( "git.lukeshu.com/btrfs-progs-ng/lib/btrfs/btrfsvol" ) +// LookupTreeRoot ////////////////////////////////////////////////////////////// + // A TreeRoot is more-or-less a btrfsitem.Root, but simpler; returned by // LookupTreeRoot. type TreeRoot struct { @@ -28,8 +30,37 @@ type TreeRoot struct { } // LookupTreeRoot is a utility function to help with implementing the -// 'TreeOperator' interface. -func LookupTreeRoot(_ context.Context, fs TreeOperator, sb Superblock, treeID btrfsprim.ObjID) (*TreeRoot, error) { +// 'Forrest' interface. +// +// The 'forrest' passed to LookupTreeRoot must handle: +// +// forrest.ForrestLookup(ctx, btrfsprim.ROOT_TREE_OBJECTID) +// +// It is OK for forrest.ForrestLookup to recurse and call +// LookupTreeRoot, as LookupTreeRoot will not call ForrestLookup for +// ROOT_TREE_OBJECTID; so it will not be an infinite recursion. +func LookupTreeRoot(ctx context.Context, forrest Forrest, sb Superblock, treeID btrfsprim.ObjID) (*TreeRoot, error) { + return OldLookupTreeRoot( + ctx, + func(rootTreeID btrfsprim.ObjID, searcher TreeSearcher) (Item, error) { + rootTree, err := forrest.ForrestLookup(ctx, rootTreeID) + if err != nil { + return Item{}, err + } + rootItem, err := rootTree.TreeSearch(ctx, searcher) + if err != nil { + return Item{}, err + } + return rootItem, nil + }, + sb, + treeID, + ) +} + +// OldLookupTreeRoot is a utility function to help with implementing +// the old 'TreeOperator' interface. +func OldLookupTreeRoot(_ context.Context, treeSearch func(treeID btrfsprim.ObjID, _ TreeSearcher) (Item, error), sb Superblock, treeID btrfsprim.ObjID) (*TreeRoot, error) { switch treeID { case btrfsprim.ROOT_TREE_OBJECTID: return &TreeRoot{ @@ -60,7 +91,7 @@ func LookupTreeRoot(_ context.Context, fs TreeOperator, sb Superblock, treeID bt Generation: sb.BlockGroupRootGeneration, }, nil default: - rootItem, err := fs.TreeSearch(btrfsprim.ROOT_TREE_OBJECTID, SearchRootItem(treeID)) + rootItem, err := treeSearch(btrfsprim.ROOT_TREE_OBJECTID, SearchRootItem(treeID)) if err != nil { if errors.Is(err, ErrNoItem) { err = fmt.Errorf("%w: %s", ErrNoTree, err) @@ -87,28 +118,50 @@ func LookupTreeRoot(_ context.Context, fs TreeOperator, sb Superblock, treeID bt } } -type TreeOperatorImpl struct { +// RawForrest ////////////////////////////////////////////////////////////////// + +// RawForrest implements Forrest. +type RawForrest struct { NodeSource NodeSource } -func (fs TreeOperatorImpl) RawTree(ctx context.Context, treeID btrfsprim.ObjID) (*RawTree, error) { - sb, err := fs.NodeSource.Superblock() +var _ Forrest = RawForrest{} + +// RawTree is a variant of ForrestLookup that returns a concrete type +// instead of an interface. +func (forrest RawForrest) RawTree(ctx context.Context, treeID btrfsprim.ObjID) (*RawTree, error) { + sb, err := forrest.NodeSource.Superblock() if err != nil { return nil, err } - rootInfo, err := LookupTreeRoot(ctx, fs, *sb, treeID) + rootInfo, err := LookupTreeRoot(ctx, forrest, *sb, treeID) if err != nil { return nil, err } return &RawTree{ - Forrest: fs, + Forrest: forrest, TreeRoot: *rootInfo, }, nil } +// ForrestLookup implements Forrest. +func (forrest RawForrest) ForrestLookup(ctx context.Context, treeID btrfsprim.ObjID) (Tree, error) { + tree, err := forrest.RawTree(ctx, treeID) + if err != nil { + return nil, err + } + return tree, nil +} + +// Compat ////////////////////////////////////////////////////////////////////// + +var _ TreeOperator = RawForrest{} + +type TreeOperatorImpl = RawForrest + // TreeWalk implements the 'TreeOperator' interface. -func (fs TreeOperatorImpl) TreeWalk(ctx context.Context, treeID btrfsprim.ObjID, errHandle func(*TreeError), cbs TreeWalkHandler) { - tree, err := fs.RawTree(ctx, treeID) +func (forrest RawForrest) TreeWalk(ctx context.Context, treeID btrfsprim.ObjID, errHandle func(*TreeError), cbs TreeWalkHandler) { + tree, err := forrest.RawTree(ctx, treeID) if err != nil { errHandle(&TreeError{Path: Path{PathRoot{TreeID: treeID}}, Err: err}) return @@ -117,9 +170,9 @@ func (fs TreeOperatorImpl) TreeWalk(ctx context.Context, treeID btrfsprim.ObjID, } // TreeLookup implements the 'TreeOperator' interface. -func (fs TreeOperatorImpl) TreeLookup(treeID btrfsprim.ObjID, key btrfsprim.Key) (Item, error) { +func (forrest RawForrest) TreeLookup(treeID btrfsprim.ObjID, key btrfsprim.Key) (Item, error) { ctx := context.TODO() - tree, err := fs.RawTree(ctx, treeID) + tree, err := forrest.RawTree(ctx, treeID) if err != nil { return Item{}, err } @@ -127,9 +180,9 @@ func (fs TreeOperatorImpl) TreeLookup(treeID btrfsprim.ObjID, key btrfsprim.Key) } // TreeSearch implements the 'TreeOperator' interface. -func (fs TreeOperatorImpl) TreeSearch(treeID btrfsprim.ObjID, searcher TreeSearcher) (Item, error) { +func (forrest RawForrest) TreeSearch(treeID btrfsprim.ObjID, searcher TreeSearcher) (Item, error) { ctx := context.TODO() - tree, err := fs.RawTree(ctx, treeID) + tree, err := forrest.RawTree(ctx, treeID) if err != nil { return Item{}, err } @@ -137,9 +190,9 @@ func (fs TreeOperatorImpl) TreeSearch(treeID btrfsprim.ObjID, searcher TreeSearc } // TreeSearchAll implements the 'TreeOperator' interface. -func (fs TreeOperatorImpl) TreeSearchAll(treeID btrfsprim.ObjID, searcher TreeSearcher) ([]Item, error) { +func (forrest RawForrest) TreeSearchAll(treeID btrfsprim.ObjID, searcher TreeSearcher) ([]Item, error) { ctx := context.TODO() - tree, err := fs.RawTree(ctx, treeID) + tree, err := forrest.RawTree(ctx, treeID) if err != nil { return nil, err } diff --git a/lib/btrfs/btrfstree/btree_tree.go b/lib/btrfs/btrfstree/btree_tree.go index 27d6548..7cfa257 100644 --- a/lib/btrfs/btrfstree/btree_tree.go +++ b/lib/btrfs/btrfstree/btree_tree.go @@ -16,11 +16,15 @@ import ( "git.lukeshu.com/btrfs-progs-ng/lib/slices" ) +// RawTree implements Tree. type RawTree struct { - Forrest TreeOperatorImpl + Forrest RawForrest TreeRoot } +var _ Tree = (*RawTree)(nil) + +// TreeWalk implements the 'Tree' interface. func (tree *RawTree) TreeWalk(ctx context.Context, cbs TreeWalkHandler) { sb, err := tree.Forrest.NodeSource.Superblock() if err != nil { @@ -161,6 +165,7 @@ func searchKP(haystack []KeyPointer, searchFn func(key btrfsprim.Key, size uint3 return KeyPointer{}, false } +// TreeSearch implements the 'Tree' interface. func (tree *RawTree) TreeSearch(ctx context.Context, searcher TreeSearcher) (Item, error) { ctx, cancel := context.WithCancel(ctx) var retErr error @@ -206,10 +211,40 @@ func (tree *RawTree) TreeSearch(ctx context.Context, searcher TreeSearcher) (Ite return ret, retErr } +// TreeLookup implements the 'Tree' interface. func (tree *RawTree) TreeLookup(ctx context.Context, key btrfsprim.Key) (Item, error) { return tree.TreeSearch(ctx, SearchExactKey(key)) } +// TreeRange implements the 'Tree' interface. +func (tree *RawTree) TreeRange(ctx context.Context, handleFn func(Item) bool) error { + ctx, cancel := context.WithCancel(ctx) + var errs derror.MultiError + + tree.TreeWalk(ctx, TreeWalkHandler{ + BadNode: func(path Path, _ *Node, err error) bool { + errs = append(errs, fmt.Errorf("%v: %w", path, err)) + return false + }, + Item: func(_ Path, item Item) { + if !handleFn(item) { + cancel() + } + }, + BadItem: func(_ Path, item Item) { + if !handleFn(item) { + cancel() + } + }, + }) + + if len(errs) > 0 { + return errs + } + return nil +} + +// TreeSubrange implements the 'Tree' interface. func (tree *RawTree) TreeSubrange(ctx context.Context, min int, searcher TreeSearcher, handleFn func(Item) bool) error { ctx, cancel := context.WithCancel(ctx) var errs derror.MultiError -- cgit v1.2.3-2-g168b From c7b6460ee9b3c07c13c973cbc8c8f690560fefc6 Mon Sep 17 00:00:00 2001 From: Luke Shumaker Date: Thu, 2 Mar 2023 16:02:42 -0700 Subject: tree-wide: Drop the old btrfstree.TreeOperator API --- lib/btrfs/btrfstree/btree.go | 53 ----------------------- lib/btrfs/btrfstree/btree_forrest.go | 81 +++--------------------------------- 2 files changed, 5 insertions(+), 129 deletions(-) (limited to 'lib/btrfs/btrfstree') diff --git a/lib/btrfs/btrfstree/btree.go b/lib/btrfs/btrfstree/btree.go index cbaa6d0..25259c0 100644 --- a/lib/btrfs/btrfstree/btree.go +++ b/lib/btrfs/btrfstree/btree.go @@ -137,59 +137,6 @@ type TreeWalkHandler struct { BadItem func(Path, Item) } -// Compat ////////////////////////////////////////////////////////////////////// - -// 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: - // - // 000 (read superblock) (maybe cbs.BadSuperblock()) - // - // 001 (read node) - // 002 cbs.Node() or cbs.BadNode() - // if interior: - // for kp in node.items: - // 003a if cbs.PreKeyPointer == nil || cbs.PreKeyPointer() { - // 004b (recurse) - // else: - // for item in node.items: - // 003b cbs.Item() or cbs.BadItem() - 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, 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. - // - // 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, search TreeSearcher) ([]Item, error) -} - -type TreeError struct { - Path Path - 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) AcquireNode(ctx context.Context, addr btrfsvol.LogicalAddr, exp NodeExpectations) (*Node, error) diff --git a/lib/btrfs/btrfstree/btree_forrest.go b/lib/btrfs/btrfstree/btree_forrest.go index 4a4a4c0..1a80504 100644 --- a/lib/btrfs/btrfstree/btree_forrest.go +++ b/lib/btrfs/btrfstree/btree_forrest.go @@ -40,27 +40,6 @@ type TreeRoot struct { // LookupTreeRoot, as LookupTreeRoot will not call ForrestLookup for // ROOT_TREE_OBJECTID; so it will not be an infinite recursion. func LookupTreeRoot(ctx context.Context, forrest Forrest, sb Superblock, treeID btrfsprim.ObjID) (*TreeRoot, error) { - return OldLookupTreeRoot( - ctx, - func(rootTreeID btrfsprim.ObjID, searcher TreeSearcher) (Item, error) { - rootTree, err := forrest.ForrestLookup(ctx, rootTreeID) - if err != nil { - return Item{}, err - } - rootItem, err := rootTree.TreeSearch(ctx, searcher) - if err != nil { - return Item{}, err - } - return rootItem, nil - }, - sb, - treeID, - ) -} - -// OldLookupTreeRoot is a utility function to help with implementing -// the old 'TreeOperator' interface. -func OldLookupTreeRoot(_ context.Context, treeSearch func(treeID btrfsprim.ObjID, _ TreeSearcher) (Item, error), sb Superblock, treeID btrfsprim.ObjID) (*TreeRoot, error) { switch treeID { case btrfsprim.ROOT_TREE_OBJECTID: return &TreeRoot{ @@ -91,7 +70,11 @@ func OldLookupTreeRoot(_ context.Context, treeSearch func(treeID btrfsprim.ObjID Generation: sb.BlockGroupRootGeneration, }, nil default: - rootItem, err := treeSearch(btrfsprim.ROOT_TREE_OBJECTID, SearchRootItem(treeID)) + rootTree, err := forrest.ForrestLookup(ctx, btrfsprim.ROOT_TREE_OBJECTID) + if err != nil { + return nil, fmt.Errorf("tree %s: %w", treeID.Format(btrfsprim.ROOT_TREE_OBJECTID), err) + } + rootItem, err := rootTree.TreeSearch(ctx, SearchRootItem(treeID)) if err != nil { if errors.Is(err, ErrNoItem) { err = fmt.Errorf("%w: %s", ErrNoTree, err) @@ -152,57 +135,3 @@ func (forrest RawForrest) ForrestLookup(ctx context.Context, treeID btrfsprim.Ob } return tree, nil } - -// Compat ////////////////////////////////////////////////////////////////////// - -var _ TreeOperator = RawForrest{} - -type TreeOperatorImpl = RawForrest - -// TreeWalk implements the 'TreeOperator' interface. -func (forrest RawForrest) TreeWalk(ctx context.Context, treeID btrfsprim.ObjID, errHandle func(*TreeError), cbs TreeWalkHandler) { - tree, err := forrest.RawTree(ctx, treeID) - if err != nil { - errHandle(&TreeError{Path: Path{PathRoot{TreeID: treeID}}, Err: err}) - return - } - tree.TreeWalk(ctx, cbs) -} - -// TreeLookup implements the 'TreeOperator' interface. -func (forrest RawForrest) TreeLookup(treeID btrfsprim.ObjID, key btrfsprim.Key) (Item, error) { - ctx := context.TODO() - tree, err := forrest.RawTree(ctx, treeID) - if err != nil { - return Item{}, err - } - return tree.TreeLookup(ctx, key) -} - -// TreeSearch implements the 'TreeOperator' interface. -func (forrest RawForrest) TreeSearch(treeID btrfsprim.ObjID, searcher TreeSearcher) (Item, error) { - ctx := context.TODO() - tree, err := forrest.RawTree(ctx, treeID) - if err != nil { - return Item{}, err - } - return tree.TreeSearch(ctx, searcher) -} - -// TreeSearchAll implements the 'TreeOperator' interface. -func (forrest RawForrest) TreeSearchAll(treeID btrfsprim.ObjID, searcher TreeSearcher) ([]Item, error) { - ctx := context.TODO() - tree, err := forrest.RawTree(ctx, treeID) - if err != nil { - return nil, err - } - - var ret []Item - err = tree.TreeSubrange(ctx, 1, searcher, func(item Item) bool { - item.Body = item.Body.CloneItem() - ret = append(ret, item) - return true - }) - - return ret, err -} -- cgit v1.2.3-2-g168b