diff options
-rw-r--r-- | lib/btrfsprogs/btrfsutil/broken_btree.go | 67 | ||||
-rw-r--r-- | lib/btrfsprogs/btrfsutil/skinny_paths.go | 106 |
2 files changed, 149 insertions, 24 deletions
diff --git a/lib/btrfsprogs/btrfsutil/broken_btree.go b/lib/btrfsprogs/btrfsutil/broken_btree.go index 8a72c74..c636b8e 100644 --- a/lib/btrfsprogs/btrfsutil/broken_btree.go +++ b/lib/btrfsprogs/btrfsutil/broken_btree.go @@ -31,28 +31,33 @@ var maxKey = btrfsprim.Key{ type treeIndex struct { TreeRootErr error Items *containers.RBTree[btrfsprim.Key, treeIndexValue] - Errors *containers.IntervalTree[btrfsprim.Key, *btrfstree.TreeError] + Errors *containers.IntervalTree[btrfsprim.Key, treeIndexError] +} + +type treeIndexError struct { + Path SkinnyPath + Err error } type treeIndexValue struct { + Path SkinnyPath Key btrfsprim.Key ItemSize uint32 - Path btrfstree.TreePath } -func newTreeIndex() treeIndex { +func newTreeIndex(arena *SkinnyPathArena) treeIndex { return treeIndex{ Items: &containers.RBTree[btrfsprim.Key, treeIndexValue]{ KeyFn: func(iv treeIndexValue) btrfsprim.Key { return iv.Key }, }, - Errors: &containers.IntervalTree[btrfsprim.Key, *btrfstree.TreeError]{ - MinFn: func(err *btrfstree.TreeError) btrfsprim.Key { - return err.Path.Node(-1).ToKey + Errors: &containers.IntervalTree[btrfsprim.Key, treeIndexError]{ + MinFn: func(err treeIndexError) btrfsprim.Key { + return arena.Inflate(err.Path).Node(-1).ToKey }, - MaxFn: func(err *btrfstree.TreeError) btrfsprim.Key { - return err.Path.Node(-1).ToMaxKey + MaxFn: func(err treeIndexError) btrfsprim.Key { + return arena.Inflate(err.Path).Node(-1).ToMaxKey }, }, } @@ -62,6 +67,8 @@ type brokenTrees struct { ctx context.Context inner *btrfs.FS + arena SkinnyPathArena + // btrfsprim.ROOT_TREE_OBJECTID rootTreeMu sync.Mutex rootTreeIndex *treeIndex @@ -130,7 +137,7 @@ func (bt *brokenTrees) treeIndex(treeID btrfsprim.ObjID) treeIndex { treeRoot, err = btrfstree.LookupTreeRoot(bt, *sb, treeID) } } - cacheEntry := newTreeIndex() + cacheEntry := newTreeIndex(&bt.arena) if err != nil { cacheEntry.TreeRootErr = err } else { @@ -144,7 +151,10 @@ func (bt *brokenTrees) treeIndex(treeID btrfsprim.ObjID) treeIndex { // 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(err) // TODO + cacheEntry.Errors.Insert(treeIndexError{ + Path: bt.arena.Deflate(err.Path), + Err: err.Err, + }) }, btrfstree.TreeWalkHandler{ Item: func(path btrfstree.TreePath, item btrfstree.Item) error { @@ -155,9 +165,9 @@ func (bt *brokenTrees) treeIndex(treeID btrfsprim.ObjID) treeIndex { panic(fmt.Errorf("dup key=%v in tree=%v", item.Key, treeID)) } cacheEntry.Items.Insert(treeIndexValue{ + Path: bt.arena.Deflate(path), Key: item.Key, ItemSize: item.BodySize, - Path: path.DeepCopy(), // TODO }) return nil }, @@ -193,17 +203,21 @@ func (bt *brokenTrees) TreeSearch(treeID btrfsprim.ObjID, fn func(btrfsprim.Key, return btrfstree.Item{}, iofs.ErrNotExist } - node, err := bt.inner.ReadNode(indexItem.Value.Path.Parent()) + itemPath := bt.arena.Inflate(indexItem.Value.Path) + node, err := bt.inner.ReadNode(itemPath.Parent()) if err != nil { return btrfstree.Item{}, err } - item := node.Data.BodyLeaf[indexItem.Value.Path.Node(-1).FromItemIdx] + item := node.Data.BodyLeaf[itemPath.Node(-1).FromItemIdx] if errs := index.Errors.SearchAll(func(k btrfsprim.Key) int { return fn(k, 0) }); len(errs) > 0 { err := make(derror.MultiError, len(errs)) for i := range errs { - err[i] = errs[i] + err[i] = &btrfstree.TreeError{ + Path: bt.arena.Inflate(errs[i].Path), + Err: errs[i].Err, + } } return item, err } @@ -226,20 +240,24 @@ func (bt *brokenTrees) TreeSearchAll(treeID btrfsprim.ObjID, fn func(btrfsprim.K ret := make([]btrfstree.Item, len(indexItems)) var node *diskio.Ref[btrfsvol.LogicalAddr, btrfstree.Node] for i := range indexItems { - if node == nil || node.Addr != indexItems[i].Path.Node(-2).ToNodeAddr { + itemPath := bt.arena.Inflate(indexItems[i].Path) + if node == nil || node.Addr != itemPath.Node(-2).ToNodeAddr { var err error - node, err = bt.inner.ReadNode(indexItems[i].Path.Parent()) + node, err = bt.inner.ReadNode(itemPath.Parent()) if err != nil { return nil, err } } - ret[i] = node.Data.BodyLeaf[indexItems[i].Path.Node(-1).FromItemIdx] + ret[i] = node.Data.BodyLeaf[itemPath.Node(-1).FromItemIdx] } if errs := index.Errors.SearchAll(func(k btrfsprim.Key) int { return fn(k, 0) }); len(errs) > 0 { err := make(derror.MultiError, len(errs)) for i := range errs { - err[i] = errs[i] + err[i] = &btrfstree.TreeError{ + Path: bt.arena.Inflate(errs[i].Path), + Err: errs[i].Err, + } } return ret, err } @@ -268,17 +286,18 @@ func (bt *brokenTrees) TreeWalk(ctx context.Context, treeID btrfsprim.ObjID, err return bt.ctx.Err() } if cbs.Item != nil { - if node == nil || node.Addr != indexItem.Value.Path.Node(-2).ToNodeAddr { + itemPath := bt.arena.Inflate(indexItem.Value.Path) + if node == nil || node.Addr != itemPath.Node(-2).ToNodeAddr { var err error - node, err = bt.inner.ReadNode(indexItem.Value.Path.Parent()) + node, err = bt.inner.ReadNode(itemPath.Parent()) if err != nil { - errHandle(&btrfstree.TreeError{Path: indexItem.Value.Path, Err: err}) + errHandle(&btrfstree.TreeError{Path: itemPath, Err: err}) return nil } } - item := node.Data.BodyLeaf[indexItem.Value.Path.Node(-1).FromItemIdx] - if err := cbs.Item(indexItem.Value.Path, item); err != nil { - errHandle(&btrfstree.TreeError{Path: indexItem.Value.Path, Err: err}) + item := node.Data.BodyLeaf[itemPath.Node(-1).FromItemIdx] + if err := cbs.Item(itemPath, item); err != nil { + errHandle(&btrfstree.TreeError{Path: itemPath, Err: err}) } } return nil diff --git a/lib/btrfsprogs/btrfsutil/skinny_paths.go b/lib/btrfsprogs/btrfsutil/skinny_paths.go new file mode 100644 index 0000000..7721137 --- /dev/null +++ b/lib/btrfsprogs/btrfsutil/skinny_paths.go @@ -0,0 +1,106 @@ +// Copyright (C) 2022 Luke Shumaker <lukeshu@lukeshu.com> +// +// SPDX-License-Identifier: GPL-2.0-or-later + +package btrfsutil + +import ( + "fmt" + + "git.lukeshu.com/btrfs-progs-ng/lib/btrfs/btrfstree" + "git.lukeshu.com/btrfs-progs-ng/lib/btrfs/btrfsvol" +) + +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 SkinnyPathArena struct { + fatKPs map[skinnyKP]btrfstree.TreePathElem + fatItems map[skinnyItem]btrfstree.TreePathElem +} + +type SkinnyPath struct { + Nodes []btrfsvol.LogicalAddr + Item int +} + +func (a *SkinnyPathArena) init() { + if a.fatKPs == nil { + a.fatKPs = make(map[skinnyKP]btrfstree.TreePathElem) + a.fatItems = make(map[skinnyItem]btrfstree.TreePathElem) + } +} + +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) + } else { + maybeSet("SkinnyPathArena.fatItems", a.fatItems, skinnyItem{ + node: prevNode, + item: elem.FromItemIdx, + }, elem) + ret.Item = elem.FromItemIdx + } + prevNode = elem.ToNodeAddr + } + + return ret +} + +func (a *SkinnyPathArena) Inflate(skinny SkinnyPath) btrfstree.TreePath { + a.init() + + var ret btrfstree.TreePath + + 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 + } + + 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)) + } + ret = append(ret, elem) + } + + return ret +} |