diff options
Diffstat (limited to 'lib')
-rw-r--r-- | lib/btrfs/btrfsprim/misc.go | 19 | ||||
-rw-r--r-- | lib/btrfs/btrfstree/ops.go | 32 | ||||
-rw-r--r-- | lib/btrfsprogs/btrfsutil/broken_btree.go | 17 | ||||
-rw-r--r-- | lib/btrfsprogs/btrfsutil/skinny_paths.go | 156 |
4 files changed, 139 insertions, 85 deletions
diff --git a/lib/btrfs/btrfsprim/misc.go b/lib/btrfs/btrfsprim/misc.go index 0ebbe19..9b3a6f8 100644 --- a/lib/btrfs/btrfsprim/misc.go +++ b/lib/btrfs/btrfsprim/misc.go @@ -6,6 +6,7 @@ package btrfsprim import ( "fmt" + "math" "time" "git.lukeshu.com/btrfs-progs-ng/lib/binstruct" @@ -25,6 +26,24 @@ func (k Key) String() string { return fmt.Sprintf("{%v %v %v}", k.ObjectID, k.ItemType, k.Offset) } +var MaxKey = Key{ + ObjectID: math.MaxUint64, + ItemType: math.MaxUint8, + Offset: math.MaxUint64, +} + +func (key Key) Mm() Key { + switch { + case key.Offset > 0: + key.Offset-- + case key.ItemType > 0: + key.ItemType-- + case key.ObjectID > 0: + key.ObjectID-- + } + return key +} + func (a Key) Cmp(b Key) int { if d := containers.NativeCmp(a.ObjectID, b.ObjectID); d != 0 { return d diff --git a/lib/btrfs/btrfstree/ops.go b/lib/btrfs/btrfstree/ops.go index 87ed37e..f2eb6f0 100644 --- a/lib/btrfs/btrfstree/ops.go +++ b/lib/btrfs/btrfstree/ops.go @@ -20,24 +20,6 @@ import ( "git.lukeshu.com/btrfs-progs-ng/lib/slices" ) -var maxKey = btrfsprim.Key{ - ObjectID: math.MaxUint64, - ItemType: math.MaxUint8, - Offset: math.MaxUint64, -} - -func keyMm(key btrfsprim.Key) btrfsprim.Key { - switch { - case key.Offset > 0: - key.Offset-- - case key.ItemType > 0: - key.ItemType-- - case key.ObjectID > 0: - key.ObjectID-- - } - return key -} - // TreeOperator is an interface for performing basic btree operations. type TreeOperator interface { // TreeWalk walks a tree, triggering callbacks for every node, @@ -118,11 +100,11 @@ type TreeOperatorImpl struct { func (fs TreeOperatorImpl) TreeWalk(ctx context.Context, treeID btrfsprim.ObjID, errHandle func(*TreeError), cbs TreeWalkHandler) { sb, err := fs.Superblock() if err != nil { - errHandle(&TreeError{Path: TreePath{{FromTree: treeID, ToMaxKey: maxKey}}, Err: err}) + errHandle(&TreeError{Path: TreePath{{FromTree: treeID, ToMaxKey: btrfsprim.MaxKey}}, Err: err}) } rootInfo, err := LookupTreeRoot(fs, *sb, treeID) if err != nil { - errHandle(&TreeError{Path: TreePath{{FromTree: treeID, ToMaxKey: maxKey}}, Err: err}) + errHandle(&TreeError{Path: TreePath{{FromTree: treeID, ToMaxKey: btrfsprim.MaxKey}}, Err: err}) return } fs.RawTreeWalk(ctx, *rootInfo, errHandle, cbs) @@ -137,7 +119,7 @@ func (fs TreeOperatorImpl) RawTreeWalk(ctx context.Context, rootInfo TreeRoot, e ToNodeAddr: rootInfo.RootNode, ToNodeGeneration: rootInfo.Generation, ToNodeLevel: rootInfo.Level, - ToMaxKey: maxKey, + ToMaxKey: btrfsprim.MaxKey, }} fs.treeWalk(ctx, path, errHandle, cbs) } @@ -191,7 +173,7 @@ func (fs TreeOperatorImpl) treeWalk(ctx context.Context, path TreePath, errHandl for i, item := range node.Data.BodyInternal { toMaxKey := path.Node(-1).ToMaxKey if i+1 < len(node.Data.BodyInternal) { - toMaxKey = keyMm(node.Data.BodyInternal[i+1].Key) + toMaxKey = node.Data.BodyInternal[i+1].Key.Mm() } itemPath := append(path, TreePathElem{ FromTree: node.Data.Head.Owner, @@ -267,7 +249,7 @@ func (fs TreeOperatorImpl) treeSearch(treeRoot TreeRoot, fn func(btrfsprim.Key, ToNodeAddr: treeRoot.RootNode, ToNodeGeneration: treeRoot.Generation, ToNodeLevel: treeRoot.Level, - ToMaxKey: maxKey, + ToMaxKey: btrfsprim.MaxKey, }} for { if path.Node(-1).ToNodeAddr == 0 { @@ -297,7 +279,7 @@ func (fs TreeOperatorImpl) treeSearch(treeRoot TreeRoot, fn func(btrfsprim.Key, } toMaxKey := path.Node(-1).ToMaxKey if lastGood+1 < len(node.Data.BodyInternal) { - toMaxKey = keyMm(node.Data.BodyInternal[lastGood+1].Key) + toMaxKey = node.Data.BodyInternal[lastGood+1].Key.Mm() } path = append(path, TreePathElem{ FromTree: node.Data.Head.Owner, @@ -445,7 +427,7 @@ func (fs TreeOperatorImpl) next(path TreePath, node *diskio.Ref[btrfsvol.Logical if node.Data.Head.Level > 0 { toMaxKey := path.Node(-1).ToMaxKey if len(node.Data.BodyInternal) > 1 { - toMaxKey = keyMm(node.Data.BodyInternal[1].Key) + toMaxKey = node.Data.BodyInternal[1].Key.Mm() } path = append(path, TreePathElem{ FromTree: node.Data.Head.Owner, diff --git a/lib/btrfsprogs/btrfsutil/broken_btree.go b/lib/btrfsprogs/btrfsutil/broken_btree.go index c636b8e..8d1c333 100644 --- a/lib/btrfsprogs/btrfsutil/broken_btree.go +++ b/lib/btrfsprogs/btrfsutil/broken_btree.go @@ -67,7 +67,7 @@ type brokenTrees struct { ctx context.Context inner *btrfs.FS - arena SkinnyPathArena + arena *SkinnyPathArena // btrfsprim.ROOT_TREE_OBJECTID rootTreeMu sync.Mutex @@ -110,6 +110,7 @@ func NewBrokenTrees(ctx context.Context, inner *btrfs.FS) interface { func (bt *brokenTrees) treeIndex(treeID btrfsprim.ObjID) treeIndex { var treeRoot *btrfstree.TreeRoot + var sb *btrfstree.Superblock var err error if treeID == btrfsprim.ROOT_TREE_OBJECTID { bt.rootTreeMu.Lock() @@ -117,7 +118,6 @@ func (bt *brokenTrees) treeIndex(treeID btrfsprim.ObjID) treeIndex { if bt.rootTreeIndex != nil { return *bt.rootTreeIndex } - var sb *btrfstree.Superblock sb, err = bt.inner.Superblock() if err == nil { treeRoot, err = btrfstree.LookupTreeRoot(bt.inner, *sb, treeID) @@ -131,13 +131,22 @@ func (bt *brokenTrees) treeIndex(treeID btrfsprim.ObjID) treeIndex { if cacheEntry, exists := bt.treeIndexes[treeID]; exists { return cacheEntry } - var sb *btrfstree.Superblock sb, err = bt.inner.Superblock() if err == nil { treeRoot, err = btrfstree.LookupTreeRoot(bt, *sb, treeID) } } - cacheEntry := newTreeIndex(&bt.arena) + if bt.arena == nil { + var _sb btrfstree.Superblock + if sb != nil { + _sb = *sb + } + bt.arena = &SkinnyPathArena{ + FS: bt.inner, + SB: _sb, + } + } + cacheEntry := newTreeIndex(bt.arena) if err != nil { cacheEntry.TreeRootErr = err } else { diff --git a/lib/btrfsprogs/btrfsutil/skinny_paths.go b/lib/btrfsprogs/btrfsutil/skinny_paths.go index 7721137..f7d1924 100644 --- a/lib/btrfsprogs/btrfsutil/skinny_paths.go +++ b/lib/btrfsprogs/btrfsutil/skinny_paths.go @@ -9,95 +9,139 @@ 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" ) -func maybeSet[K, V comparable](name string, m map[K]V, k K, v V) { - if other, conflict := m[k]; conflict && other != v { - panic(fmt.Errorf("conflict: %s %v can't have both %v and %v", name, k, other, v)) - } - m[k] = v -} - -type skinnyKP struct { - src, dst btrfsvol.LogicalAddr +type skinnyItem struct { + Node btrfsvol.LogicalAddr + Item int } -type skinnyItem struct { - node btrfsvol.LogicalAddr - item int +type SkinnyPath struct { + Root btrfsvol.LogicalAddr + Items []int } type SkinnyPathArena struct { - fatKPs map[skinnyKP]btrfstree.TreePathElem - fatItems map[skinnyItem]btrfstree.TreePathElem -} + FS diskio.File[btrfsvol.LogicalAddr] + SB btrfstree.Superblock -type SkinnyPath struct { - Nodes []btrfsvol.LogicalAddr - Item int + fatRoots map[btrfsvol.LogicalAddr]btrfstree.TreePathElem + fatItems *containers.LRUCache[skinnyItem, btrfstree.TreePathElem] } func (a *SkinnyPathArena) init() { - if a.fatKPs == nil { - a.fatKPs = make(map[skinnyKP]btrfstree.TreePathElem) - a.fatItems = make(map[skinnyItem]btrfstree.TreePathElem) + if a.fatRoots == nil { + a.fatRoots = make(map[btrfsvol.LogicalAddr]btrfstree.TreePathElem) + // This cache size is sorta arbitrary. At first I figured + // "let's allow 1GB of cached items", and figured 67bytes per + // item, that's about 16M items. But with overhead of the + // LRUCache, it's actually a lot higher than that. So then I + // cut it to .5M, and that cut my total memory use to ~8GB, + // which is a good number for me. + a.fatItems = containers.NewLRUCache[skinnyItem, btrfstree.TreePathElem](512 * 1024) } } +func (a *SkinnyPathArena) getItem(parent btrfstree.TreePath, itemIdx int) (btrfstree.TreePathElem, error) { + if itemIdx < 0 { + panic("should not happen") + } + + a.init() + + ret, ok := a.fatItems.Get(skinnyItem{ + Node: parent.Node(-1).ToNodeAddr, + Item: itemIdx, + }) + if ok { + return ret, nil + } + + node, err := btrfstree.ReadNode(a.FS, a.SB, parent.Node(-1).ToNodeAddr, btrfstree.NodeExpectations{}) + if err != nil { + return btrfstree.TreePathElem{}, err + } + if node.Data.Head.Level > 0 { + if itemIdx >= len(node.Data.BodyInternal) { + panic("should not happen") + } + for i, item := range node.Data.BodyInternal { + toMaxKey := parent.Node(-1).ToMaxKey + if i+1 < len(node.Data.BodyInternal) { + toMaxKey = node.Data.BodyInternal[i+1].Key.Mm() + } + elem := btrfstree.TreePathElem{ + FromTree: node.Data.Head.Owner, + FromItemIdx: i, + ToNodeAddr: item.BlockPtr, + ToNodeGeneration: item.Generation, + ToNodeLevel: node.Data.Head.Level - 1, + ToKey: item.Key, + ToMaxKey: toMaxKey, + } + a.fatItems.Add(skinnyItem{Node: parent.Node(-1).ToNodeAddr, Item: i}, elem) + if i == itemIdx { + ret = elem + } + } + } else { + if itemIdx >= 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, + } + a.fatItems.Add(skinnyItem{Node: parent.Node(-1).ToNodeAddr, Item: i}, elem) + if i == itemIdx { + ret = elem + } + } + } + + return ret, nil +} + func (a *SkinnyPathArena) Deflate(fat btrfstree.TreePath) SkinnyPath { a.init() var ret SkinnyPath - ret.Item = -1 var prevNode btrfsvol.LogicalAddr - for _, elem := range fat { - if elem.ToNodeAddr > 0 { - maybeSet("SkinnyPathArena.fatKPs", a.fatKPs, skinnyKP{ - src: prevNode, - dst: elem.ToNodeAddr, - }, elem) - ret.Nodes = append(ret.Nodes, elem.ToNodeAddr) + for i, elem := range fat { + if i == 0 { + a.fatRoots[elem.ToNodeAddr] = elem + ret.Root = elem.ToNodeAddr } else { - maybeSet("SkinnyPathArena.fatItems", a.fatItems, skinnyItem{ - node: prevNode, - item: elem.FromItemIdx, - }, elem) - ret.Item = elem.FromItemIdx + a.fatItems.Add(skinnyItem{Node: prevNode, Item: elem.FromItemIdx}, elem) + ret.Items = append(ret.Items, elem.FromItemIdx) } prevNode = elem.ToNodeAddr } - return ret } func (a *SkinnyPathArena) Inflate(skinny SkinnyPath) btrfstree.TreePath { a.init() - var ret btrfstree.TreePath + ret := make(btrfstree.TreePath, 0, 1+len(skinny.Items)) - var prevNode btrfsvol.LogicalAddr - for _, node := range skinny.Nodes { - elem, ok := a.fatKPs[skinnyKP{ - src: prevNode, - dst: node, - }] - if !ok { - panic(fmt.Errorf("SkinnyPathArena.Inflate: no stored TreePathElem for %v->%v", - prevNode, node)) - } - ret = append(ret, elem) - prevNode = node + root, ok := a.fatRoots[skinny.Root] + if !ok { + panic(fmt.Errorf("SkinnyPathArena.Inflate: no stored TreePathElem for root->%v", + skinny.Root)) } + ret = append(ret, root) - if skinny.Item >= 0 { - elem, ok := a.fatItems[skinnyItem{ - node: prevNode, - item: skinny.Item, - }] - if !ok { - panic(fmt.Errorf("SkinnyPathArena.Inflate: no stored TreePathElem for %v[%d]", - prevNode, skinny.Item)) + for _, itemIdx := range skinny.Items { + elem, err := a.getItem(ret, itemIdx) + if err != nil { + panic(err) } ret = append(ret, elem) } |