summaryrefslogtreecommitdiff
path: root/lib/btrfsutil
diff options
context:
space:
mode:
Diffstat (limited to 'lib/btrfsutil')
-rw-r--r--lib/btrfsutil/graph.go34
-rw-r--r--lib/btrfsutil/graph_loops.go21
-rw-r--r--lib/btrfsutil/old_rebuilt_forrest.go92
-rw-r--r--lib/btrfsutil/rebuilt_readitem.go22
-rw-r--r--lib/btrfsutil/rebuilt_tree.go8
-rw-r--r--lib/btrfsutil/skinny_paths.go38
6 files changed, 110 insertions, 105 deletions
diff --git a/lib/btrfsutil/graph.go b/lib/btrfsutil/graph.go
index 8debe9d..09a17b4 100644
--- a/lib/btrfsutil/graph.go
+++ b/lib/btrfsutil/graph.go
@@ -27,20 +27,31 @@ type GraphNode struct {
Level uint8
Generation btrfsprim.Generation
Owner btrfsprim.ObjID
- NumItems uint32
- MinItem btrfsprim.Key
- MaxItem btrfsprim.Key
Items []btrfsprim.Key
}
+func (n GraphNode) MinItem() btrfsprim.Key {
+ if len(n.Items) == 0 {
+ return btrfsprim.Key{}
+ }
+ return n.Items[0]
+}
+
+func (n GraphNode) MaxItem() btrfsprim.Key {
+ if len(n.Items) == 0 {
+ return btrfsprim.Key{}
+ }
+ return n.Items[len(n.Items)-1]
+}
+
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, n.NumItems,
- n.MinItem.ObjectID, n.MinItem.ItemType, n.MinItem.Offset,
- n.MaxItem.ObjectID, n.MaxItem.ItemType, n.MaxItem.Offset)
+ 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)
}
type GraphEdge struct {
@@ -143,9 +154,6 @@ func (g Graph) InsertNode(nodeRef *diskio.Ref[btrfsvol.LogicalAddr, btrfstree.No
Level: nodeRef.Data.Head.Level,
Generation: nodeRef.Data.Head.Generation,
Owner: nodeRef.Data.Head.Owner,
- NumItems: nodeRef.Data.Head.NumItems,
- MinItem: discardOK(nodeRef.Data.MinItem()),
- MaxItem: discardOK(nodeRef.Data.MaxItem()),
}
if nodeRef.Data.Head.Level == 0 {
@@ -175,8 +183,8 @@ func (g Graph) InsertNode(nodeRef *diskio.Ref[btrfsvol.LogicalAddr, btrfstree.No
}
} else {
g.Nodes[nodeRef.Addr] = nodeData
- kps := make([]GraphEdge, len(nodeRef.Data.BodyInternal))
- for i, kp := range nodeRef.Data.BodyInternal {
+ kps := make([]GraphEdge, len(nodeRef.Data.BodyInterior))
+ for i, kp := range nodeRef.Data.BodyInterior {
kps[i] = GraphEdge{
FromNode: nodeRef.Addr,
FromItem: i,
@@ -256,7 +264,3 @@ func (g Graph) FinalCheck(ctx context.Context, fs diskio.File[btrfsvol.LogicalAd
return nil
}
-
-func discardOK[T any](val T, _ bool) T {
- return val
-}
diff --git a/lib/btrfsutil/graph_loops.go b/lib/btrfsutil/graph_loops.go
index 3382705..b5690af 100644
--- a/lib/btrfsutil/graph_loops.go
+++ b/lib/btrfsutil/graph_loops.go
@@ -22,15 +22,15 @@ func (g Graph) renderNode(node btrfsvol.LogicalAddr) []string {
fmt.Sprintf("{addr: %v,", node),
fmt.Sprintf(" level: %v,", nodeData.Level),
fmt.Sprintf(" gen: %v,", nodeData.Generation),
- fmt.Sprintf(" num_items: %v,", nodeData.NumItems),
+ 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().ObjectID,
+ nodeData.MinItem().ItemType,
+ nodeData.MinItem().Offset),
fmt.Sprintf(" max_item: {%d,%v,%d}}",
- nodeData.MaxItem.ObjectID,
- nodeData.MaxItem.ItemType,
- nodeData.MaxItem.Offset),
+ nodeData.MaxItem().ObjectID,
+ nodeData.MaxItem().ItemType,
+ nodeData.MaxItem().Offset),
}
} else if nodeErr, ok := g.BadNodes[node]; ok {
return []string{
@@ -120,11 +120,12 @@ func checkNodeExpectations(kp GraphEdge, toNode GraphNode) error {
errs = append(errs, fmt.Errorf("kp.generation=%v != node.generation=%v",
kp.ToGeneration, toNode.Generation))
}
- if toNode.NumItems == 0 {
+ switch {
+ case len(toNode.Items) == 0:
errs = append(errs, fmt.Errorf("node.num_items=0"))
- } else if kp.ToKey != (btrfsprim.Key{}) && toNode.MinItem != kp.ToKey {
+ case kp.ToKey != (btrfsprim.Key{}) && toNode.MinItem() != kp.ToKey:
errs = append(errs, fmt.Errorf("kp.key=%v != node.items[0].key=%v",
- kp.ToKey, toNode.MinItem))
+ kp.ToKey, toNode.MinItem()))
}
if len(errs) > 0 {
return errs
diff --git a/lib/btrfsutil/old_rebuilt_forrest.go b/lib/btrfsutil/old_rebuilt_forrest.go
index 2386803..af2643a 100644
--- a/lib/btrfsutil/old_rebuilt_forrest.go
+++ b/lib/btrfsutil/old_rebuilt_forrest.go
@@ -153,40 +153,39 @@ func (bt *OldRebuiltForrest) RebuiltTree(treeID btrfsprim.ObjID) oldRebuiltTree
}
func (bt *OldRebuiltForrest) rawTreeWalk(root btrfstree.TreeRoot, cacheEntry oldRebuiltTree, walked *[]btrfsprim.Key) {
- btrfstree.TreeOperatorImpl{NodeSource: bt.inner}.RawTreeWalk(
- bt.ctx,
- root,
- func(err *btrfstree.TreeError) {
- if len(err.Path) > 0 && err.Path.Node(-1).ToNodeAddr == 0 {
- // This is a panic because on the filesystems I'm working with it more likely
- // indicates a bug in my item parser than a problem with the filesystem.
- panic(fmt.Errorf("TODO: error parsing item: %w", err))
+ errHandle := func(err *btrfstree.TreeError) {
+ if len(err.Path) > 0 && err.Path.Node(-1).ToNodeAddr == 0 {
+ // This is a panic because on the filesystems I'm working with it more likely
+ // indicates a bug in my item parser than a problem with the filesystem.
+ panic(fmt.Errorf("TODO: error parsing item: %w", err))
+ }
+ cacheEntry.Errors.Insert(oldRebuiltTreeError{
+ Path: bt.arena.Deflate(err.Path),
+ Err: err.Err,
+ })
+ }
+
+ cbs := btrfstree.TreeWalkHandler{
+ Item: func(path btrfstree.TreePath, item btrfstree.Item) error {
+ if cacheEntry.Items.Search(func(v oldRebuiltTreeValue) int { return item.Key.Compare(v.Key) }) != nil {
+ // This is a panic because I'm not really sure what the best way to
+ // handle this is, and so if this happens I want the program to crash
+ // and force me to figure out how to handle it.
+ panic(fmt.Errorf("dup key=%v in tree=%v", item.Key, root.TreeID))
}
- cacheEntry.Errors.Insert(oldRebuiltTreeError{
- Path: bt.arena.Deflate(err.Path),
- Err: err.Err,
+ cacheEntry.Items.Insert(oldRebuiltTreeValue{
+ Path: bt.arena.Deflate(path),
+ Key: item.Key,
+ ItemSize: item.BodySize,
})
+ if walked != nil {
+ *walked = append(*walked, item.Key)
+ }
+ return nil
},
- btrfstree.TreeWalkHandler{
- Item: func(path btrfstree.TreePath, item btrfstree.Item) error {
- if cacheEntry.Items.Search(func(v oldRebuiltTreeValue) int { return item.Key.Compare(v.Key) }) != nil {
- // This is a panic because I'm not really sure what the best way to
- // handle this is, and so if this happens I want the program to crash
- // and force me to figure out how to handle it.
- panic(fmt.Errorf("dup key=%v in tree=%v", item.Key, root.TreeID))
- }
- cacheEntry.Items.Insert(oldRebuiltTreeValue{
- Path: bt.arena.Deflate(path),
- Key: item.Key,
- ItemSize: item.BodySize,
- })
- if walked != nil {
- *walked = append(*walked, item.Key)
- }
- return nil
- },
- },
- )
+ }
+
+ btrfstree.TreeOperatorImpl{NodeSource: bt.inner}.RawTreeWalk(bt.ctx, root, errHandle, cbs)
}
func (bt *OldRebuiltForrest) TreeLookup(treeID btrfsprim.ObjID, key btrfsprim.Key) (btrfstree.Item, error) {
@@ -237,7 +236,7 @@ func (bt *OldRebuiltForrest) TreeSearch(treeID btrfsprim.ObjID, fn func(btrfspri
return btrfstree.Item{}, bt.addErrs(tree, fn, err)
}
- item := node.Data.BodyLeaf[itemPath.Node(-1).FromItemIdx]
+ item := node.Data.BodyLeaf[itemPath.Node(-1).FromItemSlot]
item.Body = item.Body.CloneItem()
// Since we were only asked to return 1 item, it isn't
@@ -275,7 +274,7 @@ func (bt *OldRebuiltForrest) TreeSearchAll(treeID btrfsprim.ObjID, fn func(btrfs
return nil, bt.addErrs(tree, fn, err)
}
}
- ret[i] = node.Data.BodyLeaf[itemPath.Node(-1).FromItemIdx]
+ ret[i] = node.Data.BodyLeaf[itemPath.Node(-1).FromItemSlot]
ret[i].Body = ret[i].Body.CloneItem()
}
btrfstree.FreeNodeRef(node)
@@ -295,6 +294,9 @@ func (bt *OldRebuiltForrest) TreeWalk(ctx context.Context, treeID btrfsprim.ObjI
})
return
}
+ if cbs.Item == nil {
+ return
+ }
var node *diskio.Ref[btrfsvol.LogicalAddr, btrfstree.Node]
tree.Items.Range(func(indexItem *containers.RBNode[oldRebuiltTreeValue]) bool {
if ctx.Err() != nil {
@@ -303,23 +305,21 @@ func (bt *OldRebuiltForrest) TreeWalk(ctx context.Context, treeID btrfsprim.ObjI
if bt.ctx.Err() != nil {
return false
}
- if cbs.Item != nil {
- itemPath := bt.arena.Inflate(indexItem.Value.Path)
- if node == nil || node.Addr != itemPath.Node(-2).ToNodeAddr {
- var err error
+ itemPath := bt.arena.Inflate(indexItem.Value.Path)
+ if node == nil || node.Addr != itemPath.Node(-2).ToNodeAddr {
+ var err error
+ btrfstree.FreeNodeRef(node)
+ node, err = bt.inner.ReadNode(itemPath.Parent())
+ if err != nil {
btrfstree.FreeNodeRef(node)
- node, err = bt.inner.ReadNode(itemPath.Parent())
- if err != nil {
- btrfstree.FreeNodeRef(node)
- errHandle(&btrfstree.TreeError{Path: itemPath, Err: err})
- return true
- }
- }
- item := node.Data.BodyLeaf[itemPath.Node(-1).FromItemIdx]
- if err := cbs.Item(itemPath, item); err != nil {
errHandle(&btrfstree.TreeError{Path: itemPath, Err: err})
+ return true
}
}
+ item := node.Data.BodyLeaf[itemPath.Node(-1).FromItemSlot]
+ if err := cbs.Item(itemPath, item); err != nil {
+ errHandle(&btrfstree.TreeError{Path: itemPath, Err: err})
+ }
return true
})
btrfstree.FreeNodeRef(node)
diff --git a/lib/btrfsutil/rebuilt_readitem.go b/lib/btrfsutil/rebuilt_readitem.go
index 57440cf..016299c 100644
--- a/lib/btrfsutil/rebuilt_readitem.go
+++ b/lib/btrfsutil/rebuilt_readitem.go
@@ -22,11 +22,11 @@ import (
type ItemPtr struct {
Node btrfsvol.LogicalAddr
- Idx int
+ Slot int
}
func (ptr ItemPtr) String() string {
- return fmt.Sprintf("node@%v[%v]", ptr.Node, ptr.Idx)
+ return fmt.Sprintf("node@%v[%v]", ptr.Node, ptr.Slot)
}
type SizeAndErr struct {
@@ -74,7 +74,7 @@ func (o *KeyIO) InsertNode(nodeRef *diskio.Ref[btrfsvol.LogicalAddr, btrfstree.N
for i, item := range nodeRef.Data.BodyLeaf {
ptr := ItemPtr{
Node: nodeRef.Addr,
- Idx: i,
+ Slot: i,
}
switch itemBody := item.Body.(type) {
case *btrfsitem.Inode:
@@ -141,8 +141,8 @@ func (o *KeyIO) readNode(ctx context.Context, laddr btrfsvol.LogicalAddr) *diski
}
return nil
},
- MinItem: containers.Optional[btrfsprim.Key]{OK: true, Val: graphInfo.MinItem},
- MaxItem: containers.Optional[btrfsprim.Key]{OK: true, Val: graphInfo.MaxItem},
+ MinItem: containers.Optional[btrfsprim.Key]{OK: true, Val: graphInfo.MinItem()},
+ MaxItem: containers.Optional[btrfsprim.Key]{OK: true, Val: graphInfo.MaxItem()},
})
if err != nil {
panic(fmt.Errorf("should not happen: i/o error: %w", err))
@@ -159,13 +159,13 @@ func (o *KeyIO) ReadItem(ctx context.Context, ptr ItemPtr) btrfsitem.Item {
if o.graph.Nodes[ptr.Node].Level != 0 {
panic(fmt.Errorf("should not happen: btrfsutil.KeyIO.ReadItem called for non-leaf node@%v", ptr.Node))
}
- if ptr.Idx < 0 {
- panic(fmt.Errorf("should not happen: btrfsutil.KeyIO.ReadItem called for negative item index: %v", ptr.Idx))
+ if ptr.Slot < 0 {
+ panic(fmt.Errorf("should not happen: btrfsutil.KeyIO.ReadItem called for negative item slot: %v", ptr.Slot))
}
items := o.readNode(ctx, ptr.Node).Data.BodyLeaf
- if ptr.Idx >= len(items) {
- panic(fmt.Errorf("should not happen: btrfsutil.KeyIO.ReadItem called for out-of-bounds item index: index=%v len=%v",
- ptr.Idx, len(items)))
+ if ptr.Slot >= len(items) {
+ panic(fmt.Errorf("should not happen: btrfsutil.KeyIO.ReadItem called for out-of-bounds item slot: slot=%v len=%v",
+ ptr.Slot, len(items)))
}
- return items[ptr.Idx].Body.CloneItem()
+ return items[ptr.Slot].Body.CloneItem()
}
diff --git a/lib/btrfsutil/rebuilt_tree.go b/lib/btrfsutil/rebuilt_tree.go
index 1009204..3133a9e 100644
--- a/lib/btrfsutil/rebuilt_tree.go
+++ b/lib/btrfsutil/rebuilt_tree.go
@@ -33,7 +33,7 @@ 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 LRUcache. They are all
+ // `mu`; but they live in a shared ARCache. They are all
// derived from tree.Roots, which is why it's OK if they get
// evicted.
//
@@ -42,7 +42,7 @@ type RebuiltTree struct {
// 3. tree.PotentialItems() = tree.forrest.excItems.Load(tree.ID)
}
-// LRU member 1: .leafToRoots() ////////////////////////////////////////////////////////////////////////////////////////
+// evictable member 1: .leafToRoots() //////////////////////////////////////////////////////////////////////////////////
// leafToRoots returns all leafs (lvl=0) in the filesystem that pass
// .isOwnerOK, whether or not they're in the tree.
@@ -129,7 +129,7 @@ func (tree *RebuiltTree) isOwnerOK(owner btrfsprim.ObjID, gen btrfsprim.Generati
}
}
-// LRU members 2 and 3: .Items() and .PotentialItems() /////////////////////////////////////////////////////////////////
+// evictable members 2 and 3: .Items() and .PotentialItems() ///////////////////////////////////////////////////////////
// Items returns a map of the items contained in this tree.
//
@@ -192,7 +192,7 @@ func (tree *RebuiltTree) items(ctx context.Context, cache containers.Map[btrfspr
for j, itemKey := range tree.forrest.graph.Nodes[leaf].Items {
newPtr := ItemPtr{
Node: leaf,
- Idx: j,
+ Slot: j,
}
if oldPtr, exists := index.Load(itemKey); !exists {
index.Store(itemKey, newPtr)
diff --git a/lib/btrfsutil/skinny_paths.go b/lib/btrfsutil/skinny_paths.go
index 1695990..adf539b 100644
--- a/lib/btrfsutil/skinny_paths.go
+++ b/lib/btrfsutil/skinny_paths.go
@@ -39,8 +39,8 @@ func (a *SkinnyPathArena) init() {
}
}
-func (a *SkinnyPathArena) getItem(parent btrfstree.TreePath, itemIdx int) (btrfstree.TreePathElem, error) {
- if itemIdx < 0 {
+func (a *SkinnyPathArena) getItem(parent btrfstree.TreePath, itemSlot int) (btrfstree.TreePathElem, error) {
+ if itemSlot < 0 {
panic("should not happen")
}
@@ -48,7 +48,7 @@ func (a *SkinnyPathArena) getItem(parent btrfstree.TreePath, itemIdx int) (btrfs
ret, ok := a.fatItems.Load(skinnyItem{
Node: parent.Node(-1).ToNodeAddr,
- Item: itemIdx,
+ Item: itemSlot,
})
if ok {
return ret, nil
@@ -60,17 +60,17 @@ func (a *SkinnyPathArena) getItem(parent btrfstree.TreePath, itemIdx int) (btrfs
return btrfstree.TreePathElem{}, err
}
if node.Data.Head.Level > 0 {
- if itemIdx >= len(node.Data.BodyInternal) {
+ if itemSlot >= len(node.Data.BodyInterior) {
panic("should not happen")
}
- for i, item := range node.Data.BodyInternal {
+ for i, item := range node.Data.BodyInterior {
toMaxKey := parent.Node(-1).ToMaxKey
- if i+1 < len(node.Data.BodyInternal) {
- toMaxKey = node.Data.BodyInternal[i+1].Key.Mm()
+ if i+1 < len(node.Data.BodyInterior) {
+ toMaxKey = node.Data.BodyInterior[i+1].Key.Mm()
}
elem := btrfstree.TreePathElem{
FromTree: node.Data.Head.Owner,
- FromItemIdx: i,
+ FromItemSlot: i,
ToNodeAddr: item.BlockPtr,
ToNodeGeneration: item.Generation,
ToNodeLevel: node.Data.Head.Level - 1,
@@ -78,23 +78,23 @@ func (a *SkinnyPathArena) getItem(parent btrfstree.TreePath, itemIdx int) (btrfs
ToMaxKey: toMaxKey,
}
a.fatItems.Store(skinnyItem{Node: parent.Node(-1).ToNodeAddr, Item: i}, elem)
- if i == itemIdx {
+ if i == itemSlot {
ret = elem
}
}
} else {
- if itemIdx >= len(node.Data.BodyLeaf) {
+ if itemSlot >= len(node.Data.BodyLeaf) {
panic("should not happen")
}
for i, item := range node.Data.BodyLeaf {
elem := btrfstree.TreePathElem{
- FromTree: node.Data.Head.Owner,
- FromItemIdx: i,
- ToKey: item.Key,
- ToMaxKey: item.Key,
+ FromTree: node.Data.Head.Owner,
+ FromItemSlot: i,
+ ToKey: item.Key,
+ ToMaxKey: item.Key,
}
a.fatItems.Store(skinnyItem{Node: parent.Node(-1).ToNodeAddr, Item: i}, elem)
- if i == itemIdx {
+ if i == itemSlot {
ret = elem
}
}
@@ -114,8 +114,8 @@ func (a *SkinnyPathArena) Deflate(fat btrfstree.TreePath) SkinnyPath {
a.fatRoots[elem.ToNodeAddr] = elem
ret.Root = elem.ToNodeAddr
} else {
- a.fatItems.Store(skinnyItem{Node: prevNode, Item: elem.FromItemIdx}, elem)
- ret.Items = append(ret.Items, elem.FromItemIdx)
+ a.fatItems.Store(skinnyItem{Node: prevNode, Item: elem.FromItemSlot}, elem)
+ ret.Items = append(ret.Items, elem.FromItemSlot)
}
prevNode = elem.ToNodeAddr
}
@@ -134,8 +134,8 @@ func (a *SkinnyPathArena) Inflate(skinny SkinnyPath) btrfstree.TreePath {
}
ret = append(ret, root)
- for _, itemIdx := range skinny.Items {
- elem, err := a.getItem(ret, itemIdx)
+ for _, itemSlot := range skinny.Items {
+ elem, err := a.getItem(ret, itemSlot)
if err != nil {
panic(err)
}
generated by cgit v1.2.3-2-g168b (git 2.25.1) at 2024-08-20 07:37:59 +0000