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 +++++++++++++++- lib/btrfs/io3_btree.go | 31 +++++++++++++ lib/btrfs/io4_fs.go | 2 +- 5 files changed, 221 insertions(+), 18 deletions(-) (limited to 'lib/btrfs') 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 diff --git a/lib/btrfs/io3_btree.go b/lib/btrfs/io3_btree.go index 030ea41..59e4c1d 100644 --- a/lib/btrfs/io3_btree.go +++ b/lib/btrfs/io3_btree.go @@ -12,6 +12,7 @@ import ( "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" "git.lukeshu.com/btrfs-progs-ng/lib/textui" ) @@ -73,6 +74,21 @@ func (fs *FS) readNode(_ context.Context, addr btrfsvol.LogicalAddr, nodeEntry * var _ btrfstree.NodeSource = (*FS)(nil) +// btrfstree.Forrest /////////////////////////////////////////////////////////// + +// RawTree is a variant of ForrestLookup that returns a concrete type +// instead of an interface. +func (fs *FS) RawTree(ctx context.Context, treeID btrfsprim.ObjID) (*btrfstree.RawTree, error) { + return btrfstree.RawForrest{NodeSource: fs}.RawTree(ctx, treeID) +} + +// ForrestLookup implements btree.Forrest. +func (fs *FS) ForrestLookup(ctx context.Context, treeID btrfsprim.ObjID) (btrfstree.Tree, error) { + return btrfstree.RawForrest{NodeSource: fs}.ForrestLookup(ctx, treeID) +} + +var _ btrfstree.Forrest = (*FS)(nil) + // btrfstree.TreeOperator ////////////////////////////////////////////////////// // TreeWalk implements btrfstree.TreeOperator. @@ -96,3 +112,18 @@ func (fs *FS) TreeSearchAll(treeID btrfsprim.ObjID, searcher btrfstree.TreeSearc } var _ btrfstree.TreeOperator = (*FS)(nil) + +// ReadableFS ////////////////////////////////////////////////////////////////// + +type ReadableFS interface { + btrfstree.Forrest + + Superblock() (*btrfstree.Superblock, error) + + Name() string + + // For reading file contents. + diskio.ReaderAt[btrfsvol.LogicalAddr] +} + +var _ ReadableFS = (*FS)(nil) diff --git a/lib/btrfs/io4_fs.go b/lib/btrfs/io4_fs.go index a611f35..57eca57 100644 --- a/lib/btrfs/io4_fs.go +++ b/lib/btrfs/io4_fs.go @@ -102,7 +102,7 @@ func NewSubvolume( sv.rootErr = err return sv } - rootInfo, err := btrfstree.LookupTreeRoot(ctx, sv.fs, *sb, sv.TreeID) + rootInfo, err := btrfstree.OldLookupTreeRoot(ctx, sv.fs.TreeSearch, *sb, sv.TreeID) if err != nil { sv.rootErr = err return sv -- cgit v1.2.3-2-g168b From 537800d21ae5dd4b95364457ab46d6403bb27f16 Mon Sep 17 00:00:00 2001 From: Luke Shumaker Date: Sat, 18 Mar 2023 13:01:49 -0400 Subject: btrfs: Fuss with indentation in prep for the next commit --- lib/btrfs/io2_lv.go | 47 +++++++++++++++++++++-------------------------- 1 file changed, 21 insertions(+), 26 deletions(-) (limited to 'lib/btrfs') diff --git a/lib/btrfs/io2_lv.go b/lib/btrfs/io2_lv.go index 44378a0..40fa8e9 100644 --- a/lib/btrfs/io2_lv.go +++ b/lib/btrfs/io2_lv.go @@ -162,33 +162,28 @@ func (fs *FS) initDev(ctx context.Context, sb btrfstree.Superblock) error { } } var errs derror.MultiError - fs.TreeWalk(ctx, btrfsprim.CHUNK_TREE_OBJECTID, - func(err *btrfstree.TreeError) { - errs = append(errs, err) - }, - btrfstree.TreeWalkHandler{ - Item: func(_ btrfstree.Path, item btrfstree.Item) { - if item.Key.ItemType != btrfsitem.CHUNK_ITEM_KEY { - return - } - switch itemBody := item.Body.(type) { - case *btrfsitem.Chunk: - for _, mapping := range itemBody.Mappings(item.Key) { - if err := fs.LV.AddMapping(mapping); err != nil { - errs = append(errs, err) - } - } - case *btrfsitem.Error: - // do nothing - default: - // This is a panic because the item decoder should not emit CHUNK_ITEM items as - // anything but btrfsitem.Chunk or btrfsitem.Error without this code also being - // updated. - panic(fmt.Errorf("should not happen: CHUNK_ITEM has unexpected item type: %T", itemBody)) + fs.TreeWalk(ctx, btrfsprim.CHUNK_TREE_OBJECTID, func(err *btrfstree.TreeError) { + errs = append(errs, err) + }, btrfstree.TreeWalkHandler{Item: func(_ btrfstree.Path, item btrfstree.Item) { + if item.Key.ItemType != btrfsitem.CHUNK_ITEM_KEY { + return + } + switch itemBody := item.Body.(type) { + case *btrfsitem.Chunk: + for _, mapping := range itemBody.Mappings(item.Key) { + if err := fs.LV.AddMapping(mapping); err != nil { + errs = append(errs, err) } - }, - }, - ) + } + case *btrfsitem.Error: + // do nothing + default: + // This is a panic because the item decoder should not emit CHUNK_ITEM items as + // anything but btrfsitem.Chunk or btrfsitem.Error without this code also being + // updated. + panic(fmt.Errorf("should not happen: CHUNK_ITEM has unexpected item type: %T", itemBody)) + } + }}) if len(errs) > 0 { return errs } -- cgit v1.2.3-2-g168b From 7c9de305d3dd364d6d76c8869d55a09bf80b28a8 Mon Sep 17 00:00:00 2001 From: Luke Shumaker Date: Thu, 2 Mar 2023 16:02:42 -0700 Subject: btrfs: Migrate to the new btrfstree.Forrest API --- lib/btrfs/csums.go | 9 +++++++-- lib/btrfs/io2_lv.go | 17 ++++++++++++----- lib/btrfs/io4_fs.go | 52 ++++++++++++++++++++-------------------------------- 3 files changed, 39 insertions(+), 39 deletions(-) (limited to 'lib/btrfs') diff --git a/lib/btrfs/csums.go b/lib/btrfs/csums.go index 8515d12..c5bcfd6 100644 --- a/lib/btrfs/csums.go +++ b/lib/btrfs/csums.go @@ -5,6 +5,7 @@ package btrfs import ( + "context" "fmt" "git.lukeshu.com/btrfs-progs-ng/lib/btrfs/btrfsitem" @@ -47,8 +48,12 @@ func ChecksumQualifiedPhysical(fs *FS, alg btrfssum.CSumType, paddr btrfsvol.Qua return ChecksumPhysical(dev, alg, paddr.Addr) } -func LookupCSum(fs btrfstree.TreeOperator, alg btrfssum.CSumType, laddr btrfsvol.LogicalAddr) (btrfssum.SumRun[btrfsvol.LogicalAddr], error) { - item, err := fs.TreeSearch(btrfsprim.CSUM_TREE_OBJECTID, btrfstree.SearchCSum(laddr, alg.Size())) +func LookupCSum(ctx context.Context, fs btrfstree.Forrest, alg btrfssum.CSumType, laddr btrfsvol.LogicalAddr) (btrfssum.SumRun[btrfsvol.LogicalAddr], error) { + csumTree, err := fs.ForrestLookup(ctx, btrfsprim.CSUM_TREE_OBJECTID) + if err != nil { + return btrfssum.SumRun[btrfsvol.LogicalAddr]{}, err + } + item, err := csumTree.TreeSearch(ctx, btrfstree.SearchCSum(laddr, alg.Size())) if err != nil { return btrfssum.SumRun[btrfsvol.LogicalAddr]{}, err } diff --git a/lib/btrfs/io2_lv.go b/lib/btrfs/io2_lv.go index 40fa8e9..e9de215 100644 --- a/lib/btrfs/io2_lv.go +++ b/lib/btrfs/io2_lv.go @@ -161,12 +161,15 @@ func (fs *FS) initDev(ctx context.Context, sb btrfstree.Superblock) error { } } } + chunkTree, err := fs.ForrestLookup(ctx, btrfsprim.CHUNK_TREE_OBJECTID) + if err != nil { + return err + } + var errs derror.MultiError - fs.TreeWalk(ctx, btrfsprim.CHUNK_TREE_OBJECTID, func(err *btrfstree.TreeError) { - errs = append(errs, err) - }, btrfstree.TreeWalkHandler{Item: func(_ btrfstree.Path, item btrfstree.Item) { + if err := chunkTree.TreeRange(ctx, func(item btrfstree.Item) bool { if item.Key.ItemType != btrfsitem.CHUNK_ITEM_KEY { - return + return true } switch itemBody := item.Body.(type) { case *btrfsitem.Chunk: @@ -183,10 +186,14 @@ func (fs *FS) initDev(ctx context.Context, sb btrfstree.Superblock) error { // updated. panic(fmt.Errorf("should not happen: CHUNK_ITEM has unexpected item type: %T", itemBody)) } - }}) + return true + }); err != nil { + errs = append(errs, err) + } if len(errs) > 0 { return errs } + return nil } diff --git a/lib/btrfs/io4_fs.go b/lib/btrfs/io4_fs.go index 57eca57..9b70713 100644 --- a/lib/btrfs/io4_fs.go +++ b/lib/btrfs/io4_fs.go @@ -20,7 +20,6 @@ import ( "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" "git.lukeshu.com/btrfs-progs-ng/lib/maps" "git.lukeshu.com/btrfs-progs-ng/lib/slices" "git.lukeshu.com/btrfs-progs-ng/lib/textui" @@ -63,17 +62,14 @@ type File struct { } type Subvolume struct { - ctx context.Context //nolint:containedctx // don't have an option while keeping the same API - fs interface { - btrfstree.TreeOperator - Superblock() (*btrfstree.Superblock, error) - diskio.ReaderAt[btrfsvol.LogicalAddr] - } + ctx context.Context //nolint:containedctx // don't have an option while keeping the same API + fs ReadableFS TreeID btrfsprim.ObjID noChecksums bool - rootInfo btrfstree.TreeRoot rootErr error + rootInfo btrfstree.TreeRoot + tree btrfstree.Tree bareInodeCache containers.Cache[btrfsprim.ObjID, BareInode] fullInodeCache containers.Cache[btrfsprim.ObjID, FullInode] @@ -83,31 +79,26 @@ type Subvolume struct { func NewSubvolume( ctx context.Context, - fs interface { - btrfstree.TreeOperator - Superblock() (*btrfstree.Superblock, error) - diskio.ReaderAt[btrfsvol.LogicalAddr] - }, + fs ReadableFS, treeID btrfsprim.ObjID, noChecksums bool, ) *Subvolume { sv := &Subvolume{ + ctx: ctx, fs: fs, TreeID: treeID, noChecksums: noChecksums, } - sb, err := sv.fs.Superblock() - if err != nil { - sv.rootErr = err - return sv - } - rootInfo, err := btrfstree.OldLookupTreeRoot(ctx, sv.fs.TreeSearch, *sb, sv.TreeID) + tree, err := sv.fs.ForrestLookup(ctx, sv.TreeID) if err != nil { sv.rootErr = err return sv } + sb, _ := sv.fs.Superblock() + rootInfo, _ := btrfstree.LookupTreeRoot(ctx, sv.fs, *sb, sv.TreeID) sv.rootInfo = *rootInfo + sv.tree = tree sv.bareInodeCache = containers.NewARCache[btrfsprim.ObjID, BareInode](textui.Tunable(128), containers.SourceFunc[btrfsprim.ObjID, BareInode](sv.loadBareInode)) @@ -142,11 +133,11 @@ func (sv *Subvolume) ReleaseBareInode(inode btrfsprim.ObjID) { sv.bareInodeCache.Release(inode) } -func (sv *Subvolume) loadBareInode(_ context.Context, inode btrfsprim.ObjID, val *BareInode) { +func (sv *Subvolume) loadBareInode(ctx context.Context, inode btrfsprim.ObjID, val *BareInode) { *val = BareInode{ Inode: inode, } - item, err := sv.fs.TreeLookup(sv.TreeID, btrfsprim.Key{ + item, err := sv.tree.TreeLookup(ctx, btrfsprim.Key{ ObjectID: inode, ItemType: btrfsitem.INODE_ITEM_KEY, Offset: 0, @@ -180,21 +171,14 @@ func (sv *Subvolume) ReleaseFullInode(inode btrfsprim.ObjID) { sv.fullInodeCache.Release(inode) } -func (sv *Subvolume) loadFullInode(_ context.Context, inode btrfsprim.ObjID, val *FullInode) { +func (sv *Subvolume) loadFullInode(ctx context.Context, inode btrfsprim.ObjID, val *FullInode) { *val = FullInode{ BareInode: BareInode{ Inode: inode, }, XAttrs: make(map[string]string), } - items, err := sv.fs.TreeSearchAll(sv.TreeID, btrfstree.SearchObject(inode)) - if err != nil { - val.Errs = append(val.Errs, err) - if len(items) == 0 { - return - } - } - for _, item := range items { + if err := sv.tree.TreeSubrange(ctx, 1, btrfstree.SearchObject(inode), func(item btrfstree.Item) bool { switch item.Key.ItemType { case btrfsitem.INODE_ITEM_KEY: switch itemBody := item.Body.(type) { @@ -203,7 +187,7 @@ func (sv *Subvolume) loadFullInode(_ context.Context, inode btrfsprim.ObjID, val if !reflect.DeepEqual(itemBody, *val.InodeItem) { val.Errs = append(val.Errs, fmt.Errorf("multiple inodes")) } - continue + return true } bodyCopy := itemBody.Clone() val.InodeItem = &bodyCopy @@ -222,8 +206,12 @@ func (sv *Subvolume) loadFullInode(_ context.Context, inode btrfsprim.ObjID, val panic(fmt.Errorf("should not happen: XATTR_ITEM has unexpected item type: %T", itemBody)) } default: + item.Body = item.Body.CloneItem() val.OtherItems = append(val.OtherItems, item) } + return true + }); err != nil { + val.Errs = append(val.Errs, err) } } @@ -503,7 +491,7 @@ func (file *File) maybeShortReadAt(dat []byte, off int64) (int, error) { return 0, err } if !file.SV.noChecksums { - sumRun, err := LookupCSum(file.SV.fs, sb.ChecksumType, blockBeg) + sumRun, err := LookupCSum(file.SV.ctx, file.SV.fs, sb.ChecksumType, blockBeg) if err != nil { return 0, fmt.Errorf("checksum@%v: %w", blockBeg, err) } -- 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 +++--------------------------------- lib/btrfs/io3_btree.go | 24 ----------- 3 files changed, 5 insertions(+), 153 deletions(-) (limited to 'lib/btrfs') 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 -} diff --git a/lib/btrfs/io3_btree.go b/lib/btrfs/io3_btree.go index 59e4c1d..01797df 100644 --- a/lib/btrfs/io3_btree.go +++ b/lib/btrfs/io3_btree.go @@ -89,30 +89,6 @@ func (fs *FS) ForrestLookup(ctx context.Context, treeID btrfsprim.ObjID) (btrfst var _ btrfstree.Forrest = (*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, searcher btrfstree.TreeSearcher) (btrfstree.Item, error) { - return btrfstree.TreeOperatorImpl{NodeSource: fs}.TreeSearch(treeID, searcher) -} - -// TreeSearchAll implements btrfstree.TreeOperator. -func (fs *FS) TreeSearchAll(treeID btrfsprim.ObjID, searcher btrfstree.TreeSearcher) ([]btrfstree.Item, error) { - return btrfstree.TreeOperatorImpl{NodeSource: fs}.TreeSearchAll(treeID, searcher) -} - -var _ btrfstree.TreeOperator = (*FS)(nil) - // ReadableFS ////////////////////////////////////////////////////////////////// type ReadableFS interface { -- cgit v1.2.3-2-g168b