summaryrefslogtreecommitdiff
path: root/lib/btrfsutil
diff options
context:
space:
mode:
Diffstat (limited to 'lib/btrfsutil')
-rw-r--r--lib/btrfsutil/graph.go53
-rw-r--r--lib/btrfsutil/graph_loops.go22
-rw-r--r--lib/btrfsutil/old_rebuilt_forrest.go77
-rw-r--r--lib/btrfsutil/rebuilt_forrest.go3
-rw-r--r--lib/btrfsutil/rebuilt_readitem.go4
-rw-r--r--lib/btrfsutil/rebuilt_tree.go10
6 files changed, 107 insertions, 62 deletions
diff --git a/lib/btrfsutil/graph.go b/lib/btrfsutil/graph.go
index ea33be7..fe7fe70 100644
--- a/lib/btrfsutil/graph.go
+++ b/lib/btrfsutil/graph.go
@@ -23,34 +23,52 @@ import (
)
type GraphNode struct {
+ Addr btrfsvol.LogicalAddr
Level uint8
Generation btrfsprim.Generation
Owner btrfsprim.ObjID
Items []btrfsprim.Key
}
-func (n GraphNode) MinItem() btrfsprim.Key {
- if len(n.Items) == 0 {
+func (n GraphNode) NumItems(g Graph) int {
+ switch n.Level {
+ case 0:
+ return len(n.Items)
+ default:
+ return len(g.EdgesFrom[n.Addr])
+ }
+}
+
+func (n GraphNode) MinItem(g Graph) btrfsprim.Key {
+ if n.NumItems(g) == 0 {
return btrfsprim.Key{}
}
- return n.Items[0]
+ switch n.Level {
+ case 0:
+ return n.Items[0]
+ default:
+ return g.EdgesFrom[n.Addr][0].ToKey
+ }
}
-func (n GraphNode) MaxItem() btrfsprim.Key {
- if len(n.Items) == 0 {
+func (n GraphNode) MaxItem(g Graph) btrfsprim.Key {
+ if n.NumItems(g) == 0 {
return btrfsprim.Key{}
}
- return n.Items[len(n.Items)-1]
+ switch n.Level {
+ case 0:
+ return n.Items[len(n.Items)-1]
+ default:
+ return g.EdgesFrom[n.Addr][len(g.EdgesFrom[n.Addr])-1].ToKey
+ }
}
func (n GraphNode) String() string {
if reflect.ValueOf(n).IsZero() {
return "{}"
}
- return fmt.Sprintf(`{lvl:%v, gen:%v, tree:%v, cnt:%v, min:(%v,%v,%v), max:(%v,%v,%v)}`,
- n.Level, n.Generation, n.Owner, len(n.Items),
- n.MinItem().ObjectID, n.MinItem().ItemType, n.MinItem().Offset,
- n.MaxItem().ObjectID, n.MaxItem().ItemType, n.MaxItem().Offset)
+ return fmt.Sprintf(`{lvl:%v, gen:%v, tree:%v, cnt:%v}`,
+ n.Level, n.Generation, n.Owner, len(n.Items))
}
type GraphEdge struct {
@@ -59,7 +77,7 @@ type GraphEdge struct {
// superblock.
FromRoot btrfsvol.LogicalAddr
FromNode btrfsvol.LogicalAddr
- FromItem int // only valid if one of FromRoot or FromNode is non-zero
+ FromSlot int // only valid if one of FromRoot or FromNode is non-zero
FromTree btrfsprim.ObjID
@@ -74,10 +92,10 @@ func (kp GraphEdge) String() string {
switch {
case kp.FromRoot != 0:
from = fmt.Sprintf("root@%v[%d]:%v",
- kp.FromRoot, kp.FromItem, kp.FromTree)
+ kp.FromRoot, kp.FromSlot, kp.FromTree)
case kp.FromNode != 0:
from = fmt.Sprintf("{node:%v, tree:%v}[%d]",
- kp.FromNode, kp.FromTree, kp.FromItem)
+ kp.FromNode, kp.FromTree, kp.FromSlot)
default:
from = fmt.Sprintf("superblock:%v", kp.FromTree)
}
@@ -103,8 +121,8 @@ func (g Graph) insertEdge(ptr *GraphEdge) {
if ptr.FromRoot != 0 && ptr.FromNode != 0 {
panic("kp.FromRoot and kp.FromNode should not both be set")
}
- if (ptr.FromRoot == 0 && ptr.FromNode == 0) && ptr.FromItem != 0 {
- panic("kp.FromItem should only be set if either kp.FromRoot or kp.FromItem is set")
+ if (ptr.FromRoot == 0 && ptr.FromNode == 0) && ptr.FromSlot != 0 {
+ panic("kp.FromSlot should only be set if either kp.FromRoot or kp.FromSlot is set")
}
g.EdgesFrom[ptr.FromNode] = append(g.EdgesFrom[ptr.FromNode], ptr)
g.EdgesTo[ptr.ToNode] = append(g.EdgesTo[ptr.ToNode], ptr)
@@ -150,6 +168,7 @@ func NewGraph(ctx context.Context, sb btrfstree.Superblock) Graph {
func (g Graph) InsertNode(node *btrfstree.Node) {
nodeData := GraphNode{
+ Addr: node.Head.Addr,
Level: node.Head.Level,
Generation: node.Head.Generation,
Owner: node.Head.Owner,
@@ -171,7 +190,7 @@ func (g Graph) InsertNode(node *btrfstree.Node) {
if itemBody, ok := item.Body.(*btrfsitem.Root); ok {
kps = append(kps, GraphEdge{
FromRoot: node.Head.Addr,
- FromItem: i,
+ FromSlot: i,
FromTree: item.Key.ObjectID,
ToNode: itemBody.ByteNr,
ToLevel: itemBody.Level,
@@ -186,7 +205,7 @@ func (g Graph) InsertNode(node *btrfstree.Node) {
for i, kp := range node.BodyInterior {
kps[i] = GraphEdge{
FromNode: node.Head.Addr,
- FromItem: i,
+ FromSlot: i,
FromTree: node.Head.Owner,
ToNode: kp.BlockPtr,
ToLevel: node.Head.Level - 1,
diff --git a/lib/btrfsutil/graph_loops.go b/lib/btrfsutil/graph_loops.go
index b5690af..2819482 100644
--- a/lib/btrfsutil/graph_loops.go
+++ b/lib/btrfsutil/graph_loops.go
@@ -24,13 +24,13 @@ func (g Graph) renderNode(node btrfsvol.LogicalAddr) []string {
fmt.Sprintf(" gen: %v,", nodeData.Generation),
fmt.Sprintf(" num_items: %v,", len(nodeData.Items)),
fmt.Sprintf(" min_item: {%d,%v,%d},",
- nodeData.MinItem().ObjectID,
- nodeData.MinItem().ItemType,
- nodeData.MinItem().Offset),
+ nodeData.MinItem(g).ObjectID,
+ nodeData.MinItem(g).ItemType,
+ nodeData.MinItem(g).Offset),
fmt.Sprintf(" max_item: {%d,%v,%d}}",
- nodeData.MaxItem().ObjectID,
- nodeData.MaxItem().ItemType,
- nodeData.MaxItem().Offset),
+ nodeData.MaxItem(g).ObjectID,
+ nodeData.MaxItem(g).ItemType,
+ nodeData.MaxItem(g).Offset),
}
} else if nodeErr, ok := g.BadNodes[node]; ok {
return []string{
@@ -43,7 +43,7 @@ func (g Graph) renderNode(node btrfsvol.LogicalAddr) []string {
}
func (g Graph) renderEdge(kp GraphEdge) []string {
- a := fmt.Sprintf("[%d]={", kp.FromItem)
+ a := fmt.Sprintf("[%d]={", kp.FromSlot)
b := strings.Repeat(" ", len(a))
ret := []string{
a + fmt.Sprintf("ToNode: %v,", kp.ToNode),
@@ -59,7 +59,7 @@ func (g Graph) renderEdge(kp GraphEdge) []string {
if toNode, ok := g.Nodes[kp.ToNode]; !ok {
err = g.BadNodes[kp.ToNode]
} else {
- err = checkNodeExpectations(kp, toNode)
+ err = g.loopCheckNodeExpectations(kp, toNode)
}
if err != nil {
c := strings.Repeat(" ", len(a)-1)
@@ -110,7 +110,7 @@ func (g Graph) renderLoop(stack []btrfsvol.LogicalAddr) []string {
return lines
}
-func checkNodeExpectations(kp GraphEdge, toNode GraphNode) error {
+func (g Graph) loopCheckNodeExpectations(kp GraphEdge, toNode GraphNode) error {
var errs derror.MultiError
if toNode.Level != kp.ToLevel {
errs = append(errs, fmt.Errorf("kp.level=%v != node.level=%v",
@@ -123,9 +123,9 @@ func checkNodeExpectations(kp GraphEdge, toNode GraphNode) error {
switch {
case len(toNode.Items) == 0:
errs = append(errs, fmt.Errorf("node.num_items=0"))
- case kp.ToKey != (btrfsprim.Key{}) && toNode.MinItem() != kp.ToKey:
+ case kp.ToKey != (btrfsprim.Key{}) && toNode.MinItem(g) != kp.ToKey:
errs = append(errs, fmt.Errorf("kp.key=%v != node.items[0].key=%v",
- kp.ToKey, toNode.MinItem()))
+ kp.ToKey, toNode.MinItem(g)))
}
if len(errs) > 0 {
return errs
diff --git a/lib/btrfsutil/old_rebuilt_forrest.go b/lib/btrfsutil/old_rebuilt_forrest.go
index e6a0399..9035b98 100644
--- a/lib/btrfsutil/old_rebuilt_forrest.go
+++ b/lib/btrfsutil/old_rebuilt_forrest.go
@@ -346,12 +346,13 @@ func (tree oldRebuiltTree) TreeSubrange(ctx context.Context, min int, searcher b
return err
}
-// TreeWalk implements btrfstree.Tree. It doesn't actually visit
-// nodes or keypointers (just items).
+// TreeWalk implements btrfstree.Tree. It only visits items and valid
+// leaf nodes (not the superblock, interior nodes, or bad nodes).
func (tree oldRebuiltTree) TreeWalk(ctx context.Context, cbs btrfstree.TreeWalkHandler) {
- if cbs.Item == nil && cbs.BadItem == nil {
+ if cbs.Node == nil && cbs.Item == nil && cbs.BadItem == nil {
return
}
+ visitedNodes := make(containers.Set[btrfsvol.LogicalAddr])
var node *btrfstree.Node
tree.Items.Range(func(indexItem *containers.RBNode[oldRebuiltTreeValue]) bool {
if ctx.Err() != nil {
@@ -361,34 +362,56 @@ func (tree oldRebuiltTree) TreeWalk(ctx context.Context, cbs btrfstree.TreeWalkH
if node == nil || node.Head.Addr != indexItem.Value.Node.LAddr {
tree.forrest.ReleaseNode(node)
node = tree.forrest.readNode(ctx, indexItem.Value.Node)
+ if cbs.Node != nil && !visitedNodes.Has(indexItem.Value.Node.LAddr) {
+ nodePath := btrfstree.Path{
+ btrfstree.PathRoot{
+ Tree: tree,
+ TreeID: tree.ID,
+ ToAddr: indexItem.Value.Node.LAddr,
+ ToGeneration: indexItem.Value.Node.Generation,
+ ToLevel: indexItem.Value.Node.Level,
+ },
+ }
+ cbs.Node(nodePath, node)
+ if ctx.Err() != nil {
+ return false
+ }
+ visitedNodes.Insert(indexItem.Value.Node.LAddr)
+ }
}
- item := node.BodyLeaf[indexItem.Value.Slot]
-
- itemPath := btrfstree.Path{
- btrfstree.PathRoot{
- Tree: tree,
- TreeID: tree.ID,
- ToAddr: indexItem.Value.Node.LAddr,
- ToGeneration: indexItem.Value.Node.Generation,
- ToLevel: indexItem.Value.Node.Level,
- },
- btrfstree.PathItem{
- FromTree: indexItem.Value.Node.Owner,
- FromSlot: indexItem.Value.Slot,
- ToKey: indexItem.Value.Key,
- },
- }
- switch item.Body.(type) {
- case *btrfsitem.Error:
- if cbs.BadItem != nil {
- cbs.BadItem(itemPath, item)
+
+ if cbs.Item != nil || cbs.BadItem != nil {
+ item := node.BodyLeaf[indexItem.Value.Slot]
+ itemPath := btrfstree.Path{
+ btrfstree.PathRoot{
+ Tree: tree,
+ TreeID: tree.ID,
+ ToAddr: indexItem.Value.Node.LAddr,
+ ToGeneration: indexItem.Value.Node.Generation,
+ ToLevel: indexItem.Value.Node.Level,
+ },
+ btrfstree.PathItem{
+ FromTree: indexItem.Value.Node.Owner,
+ FromSlot: indexItem.Value.Slot,
+ ToKey: indexItem.Value.Key,
+ },
}
- default:
- if cbs.Item != nil {
- cbs.Item(itemPath, item)
+ switch item.Body.(type) {
+ case *btrfsitem.Error:
+ if cbs.BadItem != nil {
+ cbs.BadItem(itemPath, item)
+ }
+ default:
+ if cbs.Item != nil {
+ cbs.Item(itemPath, item)
+ }
+ }
+ if ctx.Err() != nil {
+ return false
}
}
- return ctx.Err() == nil
+
+ return true
})
tree.forrest.ReleaseNode(node)
}
diff --git a/lib/btrfsutil/rebuilt_forrest.go b/lib/btrfsutil/rebuilt_forrest.go
index 60f3010..fcfb353 100644
--- a/lib/btrfsutil/rebuilt_forrest.go
+++ b/lib/btrfsutil/rebuilt_forrest.go
@@ -47,6 +47,9 @@ func (cb noopRebuiltForrestCallbacks) LookupRoot(ctx context.Context, tree btrfs
key.Offset = 0
return tgt.Compare(key)
})
+ if !ok {
+ return 0, btrfsitem.Root{}, false
+ }
itemBody := cb.forrest.readItem(ctx, itemPtr)
defer itemBody.Free()
switch itemBody := itemBody.(type) {
diff --git a/lib/btrfsutil/rebuilt_readitem.go b/lib/btrfsutil/rebuilt_readitem.go
index 73dc01e..80a9e4b 100644
--- a/lib/btrfsutil/rebuilt_readitem.go
+++ b/lib/btrfsutil/rebuilt_readitem.go
@@ -48,8 +48,8 @@ func (ts *RebuiltForrest) readItem(ctx context.Context, ptr ItemPtr) btrfsitem.I
}
return nil
},
- MinItem: containers.OptionalValue(graphInfo.MinItem()),
- MaxItem: containers.OptionalValue(graphInfo.MaxItem()),
+ MinItem: containers.OptionalValue(graphInfo.MinItem(ts.graph)),
+ MaxItem: containers.OptionalValue(graphInfo.MaxItem(ts.graph)),
})
defer ts.file.ReleaseNode(node)
if err != nil {
diff --git a/lib/btrfsutil/rebuilt_tree.go b/lib/btrfsutil/rebuilt_tree.go
index e65a3f6..b996bdb 100644
--- a/lib/btrfsutil/rebuilt_tree.go
+++ b/lib/btrfsutil/rebuilt_tree.go
@@ -33,13 +33,13 @@ type RebuiltTree struct {
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 ARCache. They are all
+ // `mu`; but they live in a shared Cache. They are all
// derived from tree.Roots, which is why it's OK if they get
// evicted.
//
- // 1. tree.leafToRoots() = tree.forrest.leafs.Load(tree.ID)
- // 2. tree.RebuiltItems() = tree.forrest.incItems.Load(tree.ID)
- // 3. tree.RebuiltPotentialItems() = tree.forrest.excItems.Load(tree.ID)
+ // 1. tree.leafToRoots() = tree.forrest.leafs.Acquire(tree.ID)
+ // 2. tree.RebuiltItems() = tree.forrest.incItems.Acquire(tree.ID)
+ // 3. tree.RebuiltPotentialItems() = tree.forrest.excItems.Acquire(tree.ID)
}
// evictable member 1: .leafToRoots() //////////////////////////////////////////////////////////////////////////////////
@@ -120,7 +120,7 @@ func (tree *RebuiltTree) indexNode(ctx context.Context, node btrfsvol.LogicalAdd
}
// isOwnerOK returns whether it is permissible for a node with
-// .Head.Owner=owner to be in this tree.
+// .Head.Owner=owner and .Head.Generation=gen to be in this tree.
func (tree *RebuiltTree) isOwnerOK(owner btrfsprim.ObjID, gen btrfsprim.Generation) bool {
for {
if owner == tree.ID {
generated by cgit v1.2.3-2-g168b (git 2.25.1) at 2025-03-20 18:12:40 +0000