summaryrefslogtreecommitdiff
path: root/lib
diff options
context:
space:
mode:
Diffstat (limited to 'lib')
-rw-r--r--lib/btrfsutil/rebuilt_callbacks.go8
-rw-r--r--lib/btrfsutil/rebuilt_forrest.go96
-rw-r--r--lib/btrfsutil/rebuilt_forrest_test.go193
-rw-r--r--lib/btrfsutil/rebuilt_tree.go9
4 files changed, 259 insertions, 47 deletions
diff --git a/lib/btrfsutil/rebuilt_callbacks.go b/lib/btrfsutil/rebuilt_callbacks.go
index 41fe7f1..fdc826c 100644
--- a/lib/btrfsutil/rebuilt_callbacks.go
+++ b/lib/btrfsutil/rebuilt_callbacks.go
@@ -32,8 +32,8 @@ func (noopRebuiltForrestCallbacks) AddedRoot(context.Context, btrfsprim.ObjID, b
}
func (cb noopRebuiltForrestCallbacks) LookupRoot(ctx context.Context, tree btrfsprim.ObjID) (offset btrfsprim.Generation, _item btrfsitem.Root, ok bool) {
- rootTree := cb.forrest.RebuiltTree(ctx, btrfsprim.ROOT_TREE_OBJECTID)
- if rootTree == nil {
+ rootTree, err := cb.forrest.RebuiltTree(ctx, btrfsprim.ROOT_TREE_OBJECTID)
+ if err != nil {
return 0, btrfsitem.Root{}, false
}
tgt := btrfsprim.Key{
@@ -63,8 +63,8 @@ func (cb noopRebuiltForrestCallbacks) LookupRoot(ctx context.Context, tree btrfs
}
func (cb noopRebuiltForrestCallbacks) LookupUUID(ctx context.Context, uuid btrfsprim.UUID) (id btrfsprim.ObjID, ok bool) {
- uuidTree := cb.forrest.RebuiltTree(ctx, btrfsprim.UUID_TREE_OBJECTID)
- if uuidTree == nil {
+ uuidTree, err := cb.forrest.RebuiltTree(ctx, btrfsprim.UUID_TREE_OBJECTID)
+ if err != nil {
return 0, false
}
tgt := btrfsitem.UUIDToKey(uuid)
diff --git a/lib/btrfsutil/rebuilt_forrest.go b/lib/btrfsutil/rebuilt_forrest.go
index 4249396..a4ae727 100644
--- a/lib/btrfsutil/rebuilt_forrest.go
+++ b/lib/btrfsutil/rebuilt_forrest.go
@@ -6,6 +6,7 @@ package btrfsutil
import (
"context"
+ "fmt"
"github.com/datawire/dlib/dlog"
@@ -13,6 +14,7 @@ import (
"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/maps"
"git.lukeshu.com/btrfs-progs-ng/lib/slices"
)
@@ -98,42 +100,57 @@ func NewRebuiltForrest(fs btrfs.ReadableFS, graph Graph, cb RebuiltForrestCallba
}
// RebuiltTree returns a given tree, initializing it if nescessary.
-// If it is unable to initialize the tree, then nil is returned, and
-// nothing is done to the forrest.
//
// The tree is initialized with the normal root node of the tree.
//
// This is identical to .ForrestLookup(), but returns a concrete type
// rather than an interface.
-func (ts *RebuiltForrest) RebuiltTree(ctx context.Context, treeID btrfsprim.ObjID) *RebuiltTree {
+func (ts *RebuiltForrest) RebuiltTree(ctx context.Context, treeID btrfsprim.ObjID) (*RebuiltTree, error) {
ctx = ts.treesMu.Lock(ctx)
defer ts.treesMu.Unlock()
- if !ts.addTree(ctx, treeID, nil) {
- return nil
+ ts.rebuildTree(ctx, treeID, nil)
+ tree := ts.trees[treeID]
+ if tree.ancestorLoop && tree.rootErr == nil {
+ var loop []btrfsprim.ObjID
+ for ancestor := tree; true; ancestor = ancestor.Parent {
+ loop = append(loop, ancestor.ID)
+ if slices.Contains(ancestor.ID, loop[:len(loop)-1]) {
+ break
+ }
+ }
+ tree.rootErr = fmt.Errorf("loop detected: %v", loop)
}
- return ts.trees[treeID]
+ if tree.rootErr != nil {
+ return nil, tree.rootErr
+ }
+ return tree, nil
}
-func (ts *RebuiltForrest) addTree(ctx context.Context, treeID btrfsprim.ObjID, stack []btrfsprim.ObjID) (ok bool) {
- if tree, ok := ts.trees[treeID]; ok {
- return tree != nil
+func (ts *RebuiltForrest) rebuildTree(ctx context.Context, treeID btrfsprim.ObjID, stack []btrfsprim.ObjID) {
+ loop := false
+ if maps.HasKey(ts.trees, treeID) {
+ loop = slices.Contains(treeID, stack)
+ if !loop {
+ return
+ }
}
+
+ stack = append(stack, treeID)
+ ctx = dlog.WithField(ctx, "btrfs.util.rebuilt-forrest.add-tree", stack)
defer func() {
- if !ok {
- // Store a negative cache of this. tree.RebuiltAddRoot() for the ROOT or
- // UUID trees will call .flushNegativeCache().
- ts.trees[treeID] = nil
+ if ts.trees[treeID].rootErr != nil {
+ dlog.Errorf(ctx, "failed to add tree: %v", ts.trees[treeID].rootErr)
}
}()
- stack = append(stack, treeID)
- ctx = dlog.WithField(ctx, "btrfs.util.rebuilt-forrest.add-tree", stack)
dlog.Info(ctx, "adding tree...")
- if slices.Contains(treeID, stack[:len(stack)-1]) {
- dlog.Errorf(ctx, "failed to add tree: loop detected: %v", stack)
- return false
+
+ if loop {
+ ts.trees[treeID].ancestorLoop = true
+ dlog.Error(ctx, "loop detected")
+ return
}
- tree := &RebuiltTree{
+ ts.trees[treeID] = &RebuiltTree{
ID: treeID,
Roots: make(containers.Set[btrfsvol.LogicalAddr]),
forrest: ts,
@@ -153,48 +170,43 @@ func (ts *RebuiltForrest) addTree(ctx context.Context, treeID btrfsprim.ObjID, s
sb, _ := ts.inner.Superblock()
root = sb.BlockGroupRoot
default:
- if !ts.addTree(ctx, btrfsprim.ROOT_TREE_OBJECTID, stack) {
- dlog.Error(ctx, "failed to add tree: add ROOT_TREE")
- return false
- }
rootOff, rootItem, ok := ts.cb.LookupRoot(ctx, treeID)
if !ok {
- dlog.Error(ctx, "failed to add tree: lookup ROOT_ITEM")
- return false
+ ts.trees[treeID].rootErr = fmt.Errorf("failed to look up ROOT_ITEM")
+ return
}
root = rootItem.ByteNr
- tree.UUID = rootItem.UUID
+ ts.trees[treeID].UUID = rootItem.UUID
if rootItem.ParentUUID != (btrfsprim.UUID{}) {
- tree.ParentGen = rootOff
- if !ts.addTree(ctx, btrfsprim.UUID_TREE_OBJECTID, stack) {
- return false
- }
+ ts.trees[treeID].ParentGen = rootOff
parentID, ok := ts.cb.LookupUUID(ctx, rootItem.ParentUUID)
if !ok {
- dlog.Errorf(ctx, "failed to add tree: lookup UUID %v", rootItem.ParentUUID)
- return false
+ ts.trees[treeID].rootErr = fmt.Errorf("failed to look up UUID: %v", rootItem.ParentUUID)
+ return
}
- if !ts.addTree(ctx, parentID, stack) {
- dlog.Errorf(ctx, "failed to add tree: add parent tree %v", parentID)
- return false
+ ts.rebuildTree(ctx, parentID, stack)
+ ts.trees[treeID].Parent = ts.trees[parentID]
+ switch {
+ case ts.trees[treeID].Parent.ancestorLoop:
+ ts.trees[treeID].ancestorLoop = true
+ return
+ case ts.trees[treeID].Parent.rootErr != nil:
+ ts.trees[treeID].rootErr = fmt.Errorf("failed to rebuild parent tree: %v: %w", parentID, ts.trees[treeID].Parent.rootErr)
+ return
}
- tree.Parent = ts.trees[parentID]
}
}
- ts.trees[treeID] = tree
if root != 0 {
- tree.RebuiltAddRoot(ctx, root)
+ ts.trees[treeID].RebuiltAddRoot(ctx, root)
}
-
- return true
}
func (ts *RebuiltForrest) flushNegativeCache(ctx context.Context) {
_ = ts.treesMu.Lock(ctx)
defer ts.treesMu.Unlock()
for treeID, tree := range ts.trees {
- if tree == nil {
+ if tree.rootErr != nil || tree.ancestorLoop {
delete(ts.trees, treeID)
}
}
@@ -210,7 +222,7 @@ func (ts *RebuiltForrest) RebuiltListRoots(ctx context.Context) map[btrfsprim.Ob
defer ts.treesMu.Unlock()
ret := make(map[btrfsprim.ObjID]containers.Set[btrfsvol.LogicalAddr])
for treeID, tree := range ts.trees {
- if tree != nil && len(tree.Roots) > 0 {
+ if len(tree.Roots) > 0 {
ret[treeID] = tree.Roots
}
}
diff --git a/lib/btrfsutil/rebuilt_forrest_test.go b/lib/btrfsutil/rebuilt_forrest_test.go
new file mode 100644
index 0000000..6f80eff
--- /dev/null
+++ b/lib/btrfsutil/rebuilt_forrest_test.go
@@ -0,0 +1,193 @@
+// Copyright (C) 2023 Luke Shumaker <lukeshu@lukeshu.com>
+//
+// SPDX-License-Identifier: GPL-2.0-or-later
+
+package btrfsutil
+
+import (
+ "context"
+ "testing"
+
+ "github.com/datawire/dlib/dlog"
+ "github.com/stretchr/testify/assert"
+
+ "git.lukeshu.com/btrfs-progs-ng/lib/btrfs/btrfsitem"
+ "git.lukeshu.com/btrfs-progs-ng/lib/btrfs/btrfsprim"
+ "git.lukeshu.com/btrfs-progs-ng/lib/btrfs/btrfsvol"
+)
+
+type rebuiltForrestCallbacks struct {
+ addedItem func(ctx context.Context, tree btrfsprim.ObjID, key btrfsprim.Key)
+ addedRoot func(ctx context.Context, tree btrfsprim.ObjID, root btrfsvol.LogicalAddr)
+ lookupRoot func(ctx context.Context, tree btrfsprim.ObjID) (offset btrfsprim.Generation, item btrfsitem.Root, ok bool)
+ lookupUUID func(ctx context.Context, uuid btrfsprim.UUID) (id btrfsprim.ObjID, ok bool)
+}
+
+func (cbs rebuiltForrestCallbacks) AddedItem(ctx context.Context, tree btrfsprim.ObjID, key btrfsprim.Key) {
+ cbs.addedItem(ctx, tree, key)
+}
+
+func (cbs rebuiltForrestCallbacks) AddedRoot(ctx context.Context, tree btrfsprim.ObjID, root btrfsvol.LogicalAddr) {
+ cbs.addedRoot(ctx, tree, root)
+}
+
+func (cbs rebuiltForrestCallbacks) LookupRoot(ctx context.Context, tree btrfsprim.ObjID) (offset btrfsprim.Generation, item btrfsitem.Root, ok bool) {
+ return cbs.lookupRoot(ctx, tree)
+}
+
+func (cbs rebuiltForrestCallbacks) LookupUUID(ctx context.Context, uuid btrfsprim.UUID) (id btrfsprim.ObjID, ok bool) {
+ return cbs.lookupUUID(ctx, uuid)
+}
+
+func TestRebuiltTreeCycles(t *testing.T) {
+ t.Parallel()
+
+ ctx := dlog.NewTestContext(t, true)
+
+ type mockRoot struct {
+ ID btrfsprim.ObjID
+ UUID btrfsprim.UUID
+ ParentUUID btrfsprim.UUID
+ ParentGen btrfsprim.Generation
+ }
+ roots := []mockRoot{
+ {
+ ID: 306,
+ UUID: btrfsprim.MustParseUUID("00000000-0000-0000-0000-000000000006"),
+ ParentUUID: btrfsprim.MustParseUUID("00000000-0000-0000-0000-000000000005"),
+ ParentGen: 1005,
+ },
+ {
+ ID: 305,
+ UUID: btrfsprim.MustParseUUID("00000000-0000-0000-0000-000000000005"),
+ ParentUUID: btrfsprim.MustParseUUID("00000000-0000-0000-0000-000000000004"),
+ ParentGen: 1004,
+ },
+ {
+ ID: 304,
+ UUID: btrfsprim.MustParseUUID("00000000-0000-0000-0000-000000000004"),
+ ParentUUID: btrfsprim.MustParseUUID("00000000-0000-0000-0000-000000000003"),
+ ParentGen: 1003,
+ },
+ {
+ ID: 303,
+ UUID: btrfsprim.MustParseUUID("00000000-0000-0000-0000-000000000003"),
+ ParentUUID: btrfsprim.MustParseUUID("00000000-0000-0000-0000-000000000005"),
+ ParentGen: 1002,
+ },
+ }
+
+ cbs := rebuiltForrestCallbacks{
+ addedItem: func(ctx context.Context, tree btrfsprim.ObjID, key btrfsprim.Key) {
+ // do nothing
+ },
+ addedRoot: func(ctx context.Context, tree btrfsprim.ObjID, root btrfsvol.LogicalAddr) {
+ // do nothing
+ },
+ lookupRoot: func(ctx context.Context, tree btrfsprim.ObjID) (offset btrfsprim.Generation, item btrfsitem.Root, ok bool) {
+ for _, root := range roots {
+ if root.ID == tree {
+ return root.ParentGen, btrfsitem.Root{
+ Generation: 2000,
+ UUID: root.UUID,
+ ParentUUID: root.ParentUUID,
+ }, true
+ }
+ }
+ return 0, btrfsitem.Root{}, false
+ },
+ lookupUUID: func(ctx context.Context, uuid btrfsprim.UUID) (id btrfsprim.ObjID, ok bool) {
+ for _, root := range roots {
+ if root.UUID == uuid {
+ return root.ID, true
+ }
+ }
+ return 0, false
+ },
+ }
+
+ rfs := NewRebuiltForrest(nil, Graph{}, cbs)
+
+ tree, err := rfs.RebuiltTree(ctx, 306)
+ assert.EqualError(t, err, `loop detected: [306 305 304 303 305]`)
+ assert.Nil(t, tree)
+
+ assert.NotNil(t, rfs.trees[305])
+ tree, err = rfs.RebuiltTree(ctx, 305)
+ assert.EqualError(t, err, `loop detected: [305 304 303 305]`)
+ assert.Nil(t, tree)
+
+ assert.NotNil(t, rfs.trees[304])
+ tree, err = rfs.RebuiltTree(ctx, 304)
+ assert.EqualError(t, err, `loop detected: [304 303 305 304]`)
+ assert.Nil(t, tree)
+
+ assert.NotNil(t, rfs.trees[303])
+ tree, err = rfs.RebuiltTree(ctx, 303)
+ assert.EqualError(t, err, `loop detected: [303 305 304 303]`)
+ assert.Nil(t, tree)
+}
+
+func TestRebuiltTreeParentErr(t *testing.T) {
+ t.Parallel()
+
+ ctx := dlog.NewTestContext(t, true)
+
+ type mockRoot struct {
+ ID btrfsprim.ObjID
+ UUID btrfsprim.UUID
+ ParentUUID btrfsprim.UUID
+ ParentGen btrfsprim.Generation
+ }
+ roots := []mockRoot{
+ {
+ ID: 305,
+ UUID: btrfsprim.MustParseUUID("00000000-0000-0000-0000-000000000005"),
+ ParentUUID: btrfsprim.MustParseUUID("00000000-0000-0000-0000-000000000004"),
+ ParentGen: 1004,
+ },
+ {
+ ID: 304,
+ UUID: btrfsprim.MustParseUUID("00000000-0000-0000-0000-000000000004"),
+ },
+ }
+
+ cbs := rebuiltForrestCallbacks{
+ addedItem: func(ctx context.Context, tree btrfsprim.ObjID, key btrfsprim.Key) {
+ // do nothing
+ },
+ addedRoot: func(ctx context.Context, tree btrfsprim.ObjID, root btrfsvol.LogicalAddr) {
+ // do nothing
+ },
+ lookupRoot: func(ctx context.Context, tree btrfsprim.ObjID) (offset btrfsprim.Generation, item btrfsitem.Root, ok bool) {
+ if tree == 304 {
+ // Force a fault.
+ return 0, btrfsitem.Root{}, false
+ }
+ for _, root := range roots {
+ if root.ID == tree {
+ return root.ParentGen, btrfsitem.Root{
+ Generation: 2000,
+ UUID: root.UUID,
+ ParentUUID: root.ParentUUID,
+ }, true
+ }
+ }
+ return 0, btrfsitem.Root{}, false
+ },
+ lookupUUID: func(ctx context.Context, uuid btrfsprim.UUID) (id btrfsprim.ObjID, ok bool) {
+ for _, root := range roots {
+ if root.UUID == uuid {
+ return root.ID, true
+ }
+ }
+ return 0, false
+ },
+ }
+
+ rfs := NewRebuiltForrest(nil, Graph{}, cbs)
+
+ tree, err := rfs.RebuiltTree(ctx, 305)
+ assert.EqualError(t, err, `failed to rebuild parent tree: 304: failed to look up ROOT_ITEM`)
+ assert.Nil(t, tree)
+}
diff --git a/lib/btrfsutil/rebuilt_tree.go b/lib/btrfsutil/rebuilt_tree.go
index e507851..5d38bb1 100644
--- a/lib/btrfsutil/rebuilt_tree.go
+++ b/lib/btrfsutil/rebuilt_tree.go
@@ -23,6 +23,10 @@ import (
type RebuiltTree struct {
// static
+
+ rootErr error
+ ancestorLoop bool
+
ID btrfsprim.ObjID
UUID btrfsprim.UUID
Parent *RebuiltTree
@@ -30,8 +34,11 @@ type RebuiltTree struct {
forrest *RebuiltForrest
// mutable
- mu sync.RWMutex
+
+ mu sync.RWMutex
+
Roots containers.Set[btrfsvol.LogicalAddr]
+
// There are 3 more mutable "members" that are protected by
// `mu`; but they live in a shared Cache. They are all
// derived from tree.Roots, which is why it's OK if they get
generated by cgit v1.2.3-2-g168b (git 2.25.1) at 2024-11-17 14:05:32 +0000