From 8e215721b38972c522b692032bf1c516eb62359f Mon Sep 17 00:00:00 2001 From: Luke Shumaker Date: Wed, 5 Apr 2023 10:10:34 -0600 Subject: btrfstree: Do a better job of checking node ownership This now considers the interior nodes *between* the root and the leaf, instead of just considering the root and the leaf. --- lib/btrfs/btrfstree/btree.go | 14 +++---- lib/btrfs/btrfstree/btree_tree.go | 82 +++++++++++---------------------------- lib/btrfs/btrfstree/path.go | 47 ++++++++++++++++++++-- 3 files changed, 72 insertions(+), 71 deletions(-) (limited to 'lib/btrfs') diff --git a/lib/btrfs/btrfstree/btree.go b/lib/btrfs/btrfstree/btree.go index 25259c0..e7be281 100644 --- a/lib/btrfs/btrfstree/btree.go +++ b/lib/btrfs/btrfstree/btree.go @@ -21,6 +21,11 @@ type Forrest interface { } type Tree interface { + // TreeParentID returns the ID of this tree's parent and the + // generation that this tree was split from its parent. If + // this tree has no parent, then (0, 0, nil) is returned. + TreeParentID(ctx context.Context) (btrfsprim.ObjID, btrfsprim.Generation, error) + // TreeLookup looks up the Item for a given key. // // If no such Item exists, but there is otherwise no error, @@ -70,15 +75,6 @@ type Tree interface { 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. - // - // If there is an error determining this, then `failOpen` - // 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. // diff --git a/lib/btrfs/btrfstree/btree_tree.go b/lib/btrfs/btrfstree/btree_tree.go index 7cfa257..6056ae8 100644 --- a/lib/btrfs/btrfstree/btree_tree.go +++ b/lib/btrfs/btrfstree/btree_tree.go @@ -38,7 +38,7 @@ func (tree *RawTree) TreeWalk(ctx context.Context, cbs TreeWalkHandler) { } path := Path{ PathRoot{ - Tree: tree, + Forrest: tree.Forrest, TreeID: tree.ID, ToAddr: tree.RootNode, ToGeneration: tree.Generation, @@ -317,63 +317,27 @@ func (tree *RawTree) TreeSubrange(ctx context.Context, min int, searcher TreeSea return nil } -// TreeCheckOwner implements the 'Tree' interface. -func (tree *RawTree) TreeCheckOwner(ctx context.Context, failOpen bool, owner btrfsprim.ObjID, gen btrfsprim.Generation) error { - var uuidTree *RawTree - for { - // Main. - if owner == tree.ID { - return nil - } - if tree.ParentUUID == (btrfsprim.UUID{}) { - return fmt.Errorf("owner=%v is not acceptable in this tree", - owner) - } - if gen > tree.ParentGen { - return fmt.Errorf("claimed owner=%v might be acceptable in this tree (if generation<=%v) but not with claimed generation=%v", - owner, tree.ParentGen, gen) - } - - // Loop update. - if uuidTree == nil { - var err error - uuidTree, err = tree.Forrest.RawTree(ctx, btrfsprim.UUID_TREE_OBJECTID) - if err != nil { - if failOpen { - return nil - } - return fmt.Errorf("unable to determine whether owner=%v generation=%v is acceptable: %w", - owner, gen, err) - } - } - parentIDItem, err := uuidTree.TreeLookup(ctx, btrfsitem.UUIDToKey(tree.ParentUUID)) - if err != nil { - if failOpen { - return nil - } - return fmt.Errorf("unable to determine whether owner=%v generation=%v is acceptable: %w", - owner, gen, err) - } - switch parentIDBody := parentIDItem.Body.(type) { - case *btrfsitem.UUIDMap: - tree, err = tree.Forrest.RawTree(ctx, parentIDBody.ObjID) - if err != nil { - if failOpen { - return nil - } - return fmt.Errorf("unable to determine whether owner=%v generation=%v is acceptable: %w", - owner, gen, err) - } - case *btrfsitem.Error: - if failOpen { - return nil - } - return fmt.Errorf("unable to determine whether owner=%v generation=%v is acceptable: %w", - owner, gen, parentIDBody.Err) - default: - // This is a panic because the item decoder should not emit UUID_SUBVOL items as anything but - // btrfsitem.UUIDMap or btrfsitem.Error without this code also being updated. - panic(fmt.Errorf("should not happen: UUID_SUBVOL item has unexpected type: %T", parentIDBody)) - } +// TreeParentID implements the 'Tree' interface. +func (tree *RawTree) TreeParentID(ctx context.Context) (btrfsprim.ObjID, btrfsprim.Generation, error) { + if tree.ParentUUID == (btrfsprim.UUID{}) { + return 0, 0, nil + } + uuidTree, err := tree.Forrest.RawTree(ctx, btrfsprim.UUID_TREE_OBJECTID) + if err != nil { + return 0, 0, err + } + parentIDItem, err := uuidTree.TreeLookup(ctx, btrfsitem.UUIDToKey(tree.ParentUUID)) + if err != nil { + return 0, 0, err + } + switch parentIDBody := parentIDItem.Body.(type) { + case *btrfsitem.UUIDMap: + return parentIDBody.ObjID, tree.ParentGen, nil + case *btrfsitem.Error: + return 0, 0, parentIDBody.Err + default: + // This is a panic because the item decoder should not emit UUID_SUBVOL items as anything but + // btrfsitem.UUIDMap or btrfsitem.Error without this code also being updated. + panic(fmt.Errorf("should not happen: UUID_SUBVOL item has unexpected type: %T", parentIDBody)) } } diff --git a/lib/btrfs/btrfstree/path.go b/lib/btrfs/btrfstree/path.go index 537df9a..57669ee 100644 --- a/lib/btrfs/btrfstree/path.go +++ b/lib/btrfs/btrfstree/path.go @@ -69,7 +69,7 @@ type PathElem interface { } type PathRoot struct { - Tree Tree + Forrest Forrest // It should be no surprise that these 4 members mimic the 4 // members of a 'RawTree'. TreeID btrfsprim.ObjID @@ -133,6 +133,45 @@ func (path Path) String() string { return ret.String() } +func checkOwner( + ctx context.Context, forrest Forrest, treeID btrfsprim.ObjID, failOpen bool, + ownerToCheck btrfsprim.ObjID, genToCheck btrfsprim.Generation, +) error { + for { + if ownerToCheck == treeID { + return nil + } + + tree, err := forrest.ForrestLookup(ctx, treeID) + if err != nil { + if failOpen { + return nil + } + return fmt.Errorf("unable to determine whether owner=%v generation=%v is acceptable: %w", + ownerToCheck, genToCheck, err) + } + + parentID, parentGen, err := tree.TreeParentID(ctx) + if err != nil { + if failOpen { + return nil + } + return fmt.Errorf("unable to determine whether owner=%v generation=%v is acceptable: %w", + ownerToCheck, genToCheck, err) + } + + if parentID == 0 && parentGen == 0 { + return fmt.Errorf("owner=%v is not acceptable in this tree", + ownerToCheck) + } + if genToCheck > parentGen { + return fmt.Errorf("claimed owner=%v might be acceptable in this tree (if generation<=%v) but not with claimed generation=%v", + ownerToCheck, parentGen, genToCheck) + } + treeID = parentID + } +} + // NodeExpectations returns the address to read and the expectations // to have when reading the node pointed to by this Path. // @@ -153,7 +192,8 @@ func (path Path) NodeExpectations(ctx context.Context, failOpen bool) (_ btrfsvo Level: containers.OptionalValue(lastElem.ToLevel), Generation: containers.OptionalValue(lastElem.ToGeneration), Owner: func(owner btrfsprim.ObjID, gen btrfsprim.Generation) error { - return firstElem.Tree.TreeCheckOwner(ctx, failOpen, owner, gen) + return checkOwner(ctx, firstElem.Forrest, lastElem.TreeID, failOpen, + owner, gen) }, MinItem: containers.OptionalValue(btrfsprim.Key{}), MaxItem: containers.OptionalValue(btrfsprim.MaxKey), @@ -164,7 +204,8 @@ func (path Path) NodeExpectations(ctx context.Context, failOpen bool) (_ btrfsvo Level: containers.OptionalValue(lastElem.ToLevel), Generation: containers.OptionalValue(lastElem.ToGeneration), Owner: func(owner btrfsprim.ObjID, gen btrfsprim.Generation) error { - return firstElem.Tree.TreeCheckOwner(ctx, failOpen, owner, gen) + return checkOwner(ctx, firstElem.Forrest, lastElem.FromTree, failOpen, + owner, gen) }, MinItem: containers.OptionalValue(lastElem.ToMinKey), MaxItem: containers.OptionalValue(lastElem.ToMaxKey), -- cgit v1.2.3-2-g168b From d87587a0e1d689ea1964a7de62b1e4faed120421 Mon Sep 17 00:00:00 2001 From: Luke Shumaker Date: Sun, 9 Apr 2023 18:47:44 -0600 Subject: btrfs: AcquireNode: Have expectation errors reflect the correct function --- lib/btrfs/io3_btree.go | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) (limited to 'lib/btrfs') diff --git a/lib/btrfs/io3_btree.go b/lib/btrfs/io3_btree.go index 50736cf..c9e1d79 100644 --- a/lib/btrfs/io3_btree.go +++ b/lib/btrfs/io3_btree.go @@ -44,7 +44,7 @@ func (fs *FS) AcquireNode(ctx context.Context, addr btrfsvol.LogicalAddr, exp bt if nodeEntry.node != nil { if err := exp.Check(nodeEntry.node); err != nil { fs.cacheNodes.Release(addr) - return nil, fmt.Errorf("btrfstree.ReadNode: node@%v: %w", addr, err) // fmt.Errorf("btrfs.FS.AcquireNode: node@%v: %w", addr, err) + return nil, fmt.Errorf("btrfs.FS.AcquireNode: node@%v: %w", addr, err) } } -- cgit v1.2.3-2-g168b